The availability of high-dimensional data in important application areas has made efficient tools to handle such data the need of the century. This proposal addresses some of the most basic questions arising from this need. The topics targeted in this project are on the frontier of research in algorithms, targeting well-known open problems with promising new ideas. Progress on these problems is sure to unravel mathematical structure and is likely to yield new tools. As the field of algorithms continues to expand (and extend its reach beyond computer science), such tools have become indispensable.
The PI was the founding director of the Algorithms and Randomness Center (ARC) and continues in-depth collaborations with scientists from other fields to identify problems and ideas that could play a fundamental role in understanding the complexity of computation. The topics and findings of this project will be used to design graduate courses and contribute to undergraduate ones. The graduate courses will be the basis for textbooks to benefit the research community. In addition, up-to-date surveys on these topics will be prepared by the PI and collaborators.
Sampling, Learning and Optimization in high dimension are intricately linked at many levels: reductions between problems from one topic to another, insights from one that apply to another, common analysis techniques and similar contexts (e.g., large, high-dimensional data). This project is motivated by quest for a theory of efficient algorithms, a theory that would include algorithmic tools, lower bounds and analysis techniques, in addition to questions that arise from the quest but are of independent mathematical interest and provide new ideas for classical fields.
Specifically, the project seeks to find efficient algorithms for sampling in the oracle model as well as for explicit polytopes, faster sampling and optimization using Riemannian geometry; algorithms for learning polyhedra, the analysis of neural networks with a single hidden layer, robust estimation and unsupervised learning in the presence of noise, and algorithmic considerations in the representation and analysis of very large (but not dense) graphs.
