CAREER: Geometric Phenomena in Algorithms and Complexity

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

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.