CAREER: Computation Methods

这个项目主要在两个方面进行研究。重要问题域的随机化算法。这些包括1；几何图案匹配。根据简单的二次惩罚代价函数找到数据点的最优聚类。高维混合模型的统计推断，作为硬聚类问题的一种表述。潜在的应用包括分析大型动力系统的行为模式。属性的测试。高效的几何模式匹配算法将有助于搜索压缩图像，以及在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.