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

点击翻译按钮获取中文摘要

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.