AF: Small: Fundamental High-Dimensional Algorithms based on Convex Geometry and Spectral Methods

本项目旨在发现新的算法和开发算法工具，以解决算法理论中基本的开放性问题，重点关注以下主题：(1)舍入。仿射变换在算法设计和分析中的作用，包括在强多项式时间和近似夹心凸体中求解LP的作用。(2)学习。学习多面体、学习子空间集合和识别随机图中的植团的算法。(3)等周不等式。Cheeger方法在高特征值和多分区上的推广，以及KLS超平面猜想。(4)格和凸几何。网格上的优化和采样问题，包括：(a)整数规划的复杂性（确定凸体是否与给定晶格相交），(b)切割平面方法的复杂性，以及(c)凸体中晶格点有效采样的条件。所探讨的问题具有基本性质，并且起源于许多领域，包括优化（离散和连续），采样，机器学习和数据挖掘。随着重要应用领域中高维数据可用性的增加，处理此类数据的有效工具是必要的。这个奖项解决了由于这种需求而产生的一些最基本的问题。PI是算法和随机性中心（ARC）的活跃成员，担任其创始主任，并继续与来自各个领域的科学家进行深入合作，以确定可能在理解计算复杂性方面发挥根本作用的问题和想法。该项目将为研究生课程提供在线笔记、教科书和最新的调查文章。

This project seeks to discover new algorithms and develop algorithmic tools to address fundamental open problems in the theory of algorithms under the following focus topics: (1) Rounding. The power of affine transformations in the design of algorithms and in their analysis, including for solving LP's in strongly polynomial time and approximately sandwiching convex bodies. (2) Learning. Algorithms for learning polyhedra, learning subspace juntas and identifying planted cliques in random graphs. (3) Isoperimetric inequalities. Extensions of Cheeger's method to higher eigenvalues and multi-partitions, and the KLS hyperplane conjecture. (4) Lattices and convex geometry. Optimization and sampling problems over lattices, including: (a) the complexity of integer programming (determining whether a convex body intersects a given lattice), (b) the complexity of cutting plane methods, and (c) conditions under which lattice points in a convex body be sampled efficiently.The problems explored are of a basic nature, and originate from many areas, including optimization (both discrete and continuous), sampling, machine learning and data mining. With the increasing availability of high-dimensional data in important application areas, efficient tools to handle such data are a necessity. This award addresses some of the most basic questions arising from this need. The PI, an active member of the Algorithms and Randomness Center (ARC), served as its founding director and continues in-depth collaborations with scientists from various fields to identify problems and ideas that could play a fundamental role in understanding the complexity of computation. The project will contribute to graduate courses with online notes, textbooks and up-to-date survey articles.