Fundamental Algorithms based on Random Sampling, Convex Relaxation, and Spectral Analysis

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

Randomness and geometry play a central role in the discovery of polynomial- time algorithms for fundamental problems. This project develops a set of algorithmic tools to tackle problems on the frontier of research in algorithms.The problems explored here are of a basic nature and originate from many areas, including sampling, optimization (both discrete and continuous), machine learning and data mining. Progress on these problems, in addition to its potential practical impact, unravels deep mathematical structure and yields newanalysis tools. As the yield of algorithms grows rapidly and extends its reach far beyond computer science, such tools play an important role in forming a theory of algorithms. The research results of this project contribute to several courses (with notes available online) and the graduate courses are the basis fortextbooks to benefit the research community.The tools developed by this project are based on randomness and geometry. Three specific approaches are studied | (a) sampling high-dimensional distributions by random walks, (b) convex relaxation of discrete sets and (c) spectral projection. Fundamental problems have been solved by these techniques (yielding effcient algorithms), including volume computation, convex optimization, approximation algorithms for some NP-hard discrete optimization problems and learning mixtures of distributions. The project addressesthe scope and effciency of these techniques and tackles basic open problems in the process. These include: what functions can be sampled effciently by the random walk approach? what is the complexity of volume computation? is the asymmetric TSP harder than the the symmetric version? what are the limitsof the spectral method?