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.