CAREER: Computation Methods

职业：计算方法

• 批准号: 9876172
• 负责人: Leonard Schulman
• 金额: $ 25.13万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-06-01 至 2000-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9876172&HistoricalAwards=false
• 关键词: CAREER; Computation; Methods

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.

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