This project addresses fundamental open problems in the theory of algorithms using tools from convex geometry, spectral analysis and complexity. The research will also provide algorithmic insights into central questions in functional analysis and probability. The problems tackled are of a basic nature, and originate from many areas, including sampling, optimization (both discrete and continuous), machine learning and data mining. With the abundance of high-dimensional data in important application areas, the need for efficient tools to handle such data is pressing and this project addresses the most basic questions arising from this need. Progress on these problems is sure to unravel deep mathematical structure and yield new analytical tools. As the field of algorithms continues to expand (and extends its reach far beyond computer science), such tools will play an important role in forming a theory of algorithms. The PI currently serves as the director of the Algorithms and Randomness Center, founded in 2006 on the premise of outreach to scientists and engineers and to identify problems and ideas that could play a fundamental role in computational complexity theory. The research results form the basis of courses at both the undergraduate and graduate level with materials available online.
The project has four focus topics: (1) Complexity of tensor optimization. Does there exist a polynomial-time algorithm for computing the spectral norm of an r-fold tensor? (2) Affine-invariant algorithms. Can linear programs be solved in strongly polynomial time? What is a natural affine-invariant and noise-tolerant version of principal components analysis? (3) Complexity of sampling high-dimensional distributions, both upper and lower bounds. What classes of nonconvex bodies can be sampled (optimized, integrated over) efficiently? Do there exist polynomial-time better-than-exponential approximations to the shortest lattice vector? (4) Learnability of high-dimensional functions. Can the intersection of two halfspaces be PAC-learned? Can the intersection of a polynomial number of halfspaces be learned under a Gaussian distribution?
