Geometric Tools for Algorithms

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

Title: Geometric Tools for AlgorithmsThe goal of this project is to develop a set of general algorithmic toolsbased on geometry and randomness. Four specific approaches will beinvestigated -- geometric random walks, convex relaxations, randomprojection and spectral projection. There are basic problems that can besolved by each technique (i.e., yielding efficient algorithms). Theseinclude convex optimization, approximation algorithms for NP-hard problemsand learning mixtures of distributions. The solutions to these problemslead to several questions about the applicability and efficiency of thesetechniques (e.g. What functions can be sampled efficiently by the randomwalk approach? How quickly can the volume be computed? Is there arelaxation refinement method that improves the integrality gap? What arethe limits of the spectral method?). The PI plans to address thesequestions and use the answers to tackle basic open problems in algorithms.Intellectual merit:Geometric insights and approaches play an increasingly central role in thediscovery of polynomial-time algorithms for fundamental problems. At atime when the field of algorithms is growing rapidly, such tools will becrucial in crystallizing a theory of algorithms that will deepen ourunderstanding as well as advance the field by aiding in the solution ofkey open problems.Broad impact:The problems this proposal sets out to explore are of a basic nature, andoriginate from a variety of areas, including combinatorial optimization,machine learning, information retrieval, and Euclidean geometry. Progresson these problems, in addition to its potential practical impact, is sureto unravel combinatorial/geometric structure, and is likely to yield newanalysis tools. The research results will form the basis of anundergraduate course on combinatorial optimization as well as two graduatecourses; course notes for all of these will be available online.