报告人简介：

专长和学术成就：算法设计，计算几何，组合优化，及他们在医学图像，治疗规划，及诊断 ，生物 ， 网络与移动计算，大规模集成电路设计 等方面的应用。在这些方向的国际期刊和会议上发表了140余篇论文，大部分出现在国际顶级期刊和会议中。解决了几个长期公开的问题和猜想。推广了一类最基本的几何结构和经典问题。

工作单位及主要简历：于1992年和1995获得中国科技大学，计算机科学本科和硕士学位。于2000年获得美国圣母大学（University of Notre Dame）计算机科学与工程博士学位。同年获美国纽约州立大学（布法罗）计算机科学与工程系助理教授职位，现为该系终身正教授。

1.报告题目: Sub-linear Time Hybrid Approximations for Least Trimmed Squares Estimator and Related Problems

  报告时间：2015年7月31日下午14:00

  报告地点：理工楼555

Abstract：Least Trimmed Squares (LTS) estimator is a statistical tool for estimating how well a set of points fits a hyperplane. As a robust alternative to the classical least squares estimator, LTS takes as input a set P of n points in Rd and a fitting parameter m ≤ n, and computes a non-vertical hyperplane H so that the sum of the m smallest squared vertical distances from P to H is minimized. Previous research has indicated that although solving LTS (exactly or approximately) could be quite costly (i.e., it may take Ω(nd−1) time to even approximate it when m/n is a positive constant c < 1), a hybrid version of approximation, which is a bi-criteria on residual approximation and quantile approximation, can be obtained in linear time in any fixed dimensional space. In this paper, we further show that an (&epsis;r, &epsis;q)-hybrid approximation of LTS can be computed in sub-linear time, where &epsis;r > 0 is the residual approximation ratio and 0 < &epsis;q < 1 is the quantile approximation ratio. The running time is independent of the input size n, when m = ?(n). Comparing to existing result, our approach has quite a few advantages, e.g., is much simpler, has better robustness, takes only constant additional space, and can deal with big data (e.g., streaming data). Our result is based on new insights to the problem and several novel techniques, such as recursive slab partition, sequential orthogonal rotation, and symmetric sampling. Our technique can also be extended to achieve sub-linear time hybrid approximations for several related problems, such as data-oblivious computation for LTS in Secure Multi-party Computation (SMC) protocol, LTS on uncertain and range data, and the Orthogonal Least Trimmed Squares (OLTS) problem. It is likely that our technique will be applicable to other shape fitting problems.

2.报告题目: K-Prototype Learning for 3D Rigid Structures

  报告时间：2015年8月2日下午14:00

  报告地点：理工楼555

Abstract：In this paper, we study the following new variant of prototype learning, called {K -prototype learning problem for 3D rigid structures}: Given a set of 3D rigid structures, find a set of rigid structures so that each of them is a prototype for a cluster of the given rigid structures and the total cost (or dissimilarity) is minimized. Prototype learning is a core problem in machine learning and has a wide range of applications in many areas. Existing results on this problem have mainly focused on the graph domain. In this paper, we present the first algorithm for learning multiple prototypes from 3D rigid structures. Our result is based on a number of new insights to rigid structures alignment, clustering, and prototype reconstruction, and is practically efficient with quality guarantee. We validate our approach using two type of data sets, random data and biological data of chromosome territories. Experiments suggest that our approach can effectively learn prototypes in both types of data.