CAREER: Computation Methods

CCR-9876172 Schulman该项目在两个主要领域进行研究。 重要问题域的随机算法。 这些措施包括1. 几何图案匹配2.针对一个简单的二次惩罚代价函数，找到数据点的最优聚类.高维混合模型的统计推断，作为硬聚类问题的一种形式。 潜在的应用包括分析大型动力系统的行为模式.性能测试。高效的几何模式匹配算法对于在压缩图像中以及在CAD/CAM系统中生成的几何模型中进行搜索非常有用。 当需要分析和分类大型数据列时，将应用良好的聚类算法，例如在包括统计学在内的学科中。 人口统计学、经济学、农业、心理学、机器视觉。 生物学（包括分类学和蛋白质分类）和引用模式分析（用于科学文献或万维网的超链接结构）。 2.量子计算。 所追求的问题是1.大规模量子计算的可行性。 量子计算机的现有设计提供了具有仔细可控的哈密顿量的小系统，但这些设计并不能扩展到具有足够自由度的设备来进行有趣的计算。 将进行研究以克服这一障碍。量子算法。 某些问题，包括因式分解，可以在量子计算机上以指数方式比最知名的经典方法更快地解决。 工作是追求探索量子算法的能力。量子密码原语。 量子计算机计算能力的另一面是它们能够击败当前领先的密码学方法。 工作是追求设计量子单向函数和其他密码原语的候选人。教育部分包括强调开放式作业要求学生的创造力。算法课程的扩展，以涵盖编码和数据压缩的重要方法。缩小理论和实践之间的课程差距。在课堂上使用新技术。启动本科生研究。

CCR-9876172SchulmanThis project pursues research in two main arenas.1. Randomized algorithms for important problem domains. These include 1. Geometric pattern matching2. Finding optimal clusterings of data points with respect to a simple quadratic-penalty cost function.3. Statistical inference of high of dimensional mixture models, as a formulation of hard clustering problems. Potential applications include analysis of behavior modes of large dynamical systems.4. Property testing.Highly efficient algorithms for geometric pattern matching will be useful for searching in compressed images, as well as in geometric models produced in CAD/CAM systems. Good clustering algorithms will be applied when large columns of data need to be analyzed and categorized, as is the case in disciplines including Statistics. Demographics, Economics, Agriculture, Psychology, Machine Vision. Biology (both for taxonomy and for protein classification), and citation pattern analysis (for the scientific literature or the hyperlink structure of the world wide web). 2. Quantum computation. Problems pursued are1. Feasibility of large-scale quantum computation. Existing designs for quantum computers provide small systems with carefully controllable Hamiltonians, but these do not scale to devices with enough degrees of freedom to carry out interesting computations. Research will be conducted in order to surmount this obstacle.2. Quantum algorithms. Certain problems, including factorization, can be solved on a quantum computer exponentially more rapidly than in the best known classical methods. Work is pursued exploring the capabilities of quantum algorithms.3. Quantum cryptographic primitives. The flip side of the computational power of quantum computers is their ability to defeat the current leading crytographic methods. Work is pursued on devising candidates for quantum one-way functions and other cryptographic primitives.The educational component includesAn emphasis on open-ended assignments calling for student creativity.Extension of the algorithms curriculum to cover important methods in coding and data compression.Narrowing the curricular divide between theory and practice.Use of new technologies in the classroom.Initiation of undergraduate research.