CAREER: Geometric Phenomena in Algorithms and Complexity

职业：算法和复杂性中的几何现象

• 批准号: 0644037
• 负责人: James Lee
• 金额: $ 40万
• 依托单位: University of Washington
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-02-01 至 2012-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0644037&HistoricalAwards=false
• 关键词: CAREER; Geometric; Phenomena; Algorithms; Complexity

This research involves the use of high-dimensional geometry in attacking problems at the forefront of computer science. This includes closing fundamental gaps in our understanding of theoretical issues, as well as solving practical problems that arise from the need to analyze and manipulate massive data sets. Such data sets arise naturally in disparate fields like machine learning, computer vision, and bioinformatics.On the foundational side, high-dimensional geometric techniques play a pivotal role in obtaining fast, approximate solutions to classical hard problems which are difficult to solve exactly.The investigator will study these connections and the development of new algorithmic techniques to exploit them.More specifically, the PI will seek new algorithms which provide better approximate solutions to a variety of classical problems in areas such as graph partitioning, data clustering, and graph coloring. Many of these approaches are based on semi-definite programming and an important goal of the project is to understand exactly the power that this class of algorithms provides, via both new algorithmic techniques and complexity-theoretic lower bounds. These endeavors will incorporate techniques from high-dimensional geometry and probability, functional analysis, and extremal combinatorics. Another goal concerns coping with the dimensionality of data sets. For this purpose, the goal is to develop both new dimension reduction techniques, as well as algorithms and data structure that are able to operate directly on intrinsic low-dimensional structures inside data whose representation is, a priori, high-dimensional.

这项研究涉及使用高维几何在计算机科学的前沿攻击问题。 这包括缩小我们对理论问题理解的根本差距，以及解决因分析和操作大量数据集而产生的实际问题。 这些数据集自然出现在不同的领域，如机器学习，计算机视觉和生物信息学。在基础方面，高维几何技术在获得难以精确解决的经典难题的快速近似解决方案方面发挥着关键作用。研究人员将研究这些联系以及开发新的算法技术来利用它们。更具体地说，PI将寻求新的算法，为诸如图划分、数据聚类和图着色等领域的各种经典问题提供更好的近似解决方案。 许多这些方法是基于半定规划和该项目的一个重要目标是准确地了解这类算法提供的权力，通过新的算法技术和复杂性理论的下限。 这些努力将结合技术，从高维几何和概率，功能分析，极值组合。 另一个目标涉及处理数据集的维度。 为此目的，我们的目标是开发新的降维技术，以及算法和数据结构，能够直接对数据内部的内在低维结构进行操作，其表示是先验的，高维的。