The goal of this project is to develop a set of general algorithmic tools based on geometry and randomness. Four specific approaches will be investigated -- geometric random walks, convex relaxations, random projection and spectral projection. There are basic problems that can be solved by each technique (i.e., yielding efficient algorithms). These include convex optimization, approximation algorithms for NP-hard problems and learning mixtures of distributions. The solutions to these problems lead to several questions about the applicability and efficiency of these techniques (e.g. What functions can be sampled efficiently by the random walk approach? How quickly can the volume be computed? Is there a relaxation refinement method that improves the integrality gap? What are the limits of the spectral method?). The PI plans to address these questions and use the answers to tackle basic open problems in algorithms.
Intellectual merit: Geometric insights and approaches play an increasingly central role in the discovery of polynomial-time algorithms for fundamental problems. At a time when the field of algorithms is growing rapidly, such tools will be crucial in crystallizing a theory of algorithms that will deepen our understanding as well as advance the field by aiding in the solution of key open problems.
Broad impact: The problems this proposal sets out to explore are of a basic nature, and originate from a variety of areas, including combinatorial optimization, machine learning, information retrieval, and Euclidean geometry. Progress on these problems, in addition to its potential practical impact, is sure to unravel combinatorial/geometric structure, and is likely to yield new analysis tools. The research results will form the basis of an undergraduate course on combinatorial optimization as well as two graduate courses; course notes for all of these will be available online.
