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

随机和几何在基本问题的多项式时间算法的发现中起着中心作用。本项目开发了一套算法工具来解决算法研究的前沿问题。这里探讨的问题是一个基本的性质，起源于许多领域，包括采样，优化（离散和连续），机器学习和数据挖掘。这些问题的进展，除了其潜在的实际影响外，还揭示了深层的数学结构，并产生了新的分析工具。随着算法的产量迅速增长，其影响范围远远超出计算机科学，这些工具在形成算法理论方面发挥着重要作用。该项目的研究成果有助于几门课程（有在线笔记），研究生课程是教科书的基础，使研究团体受益。这个项目开发的工具是基于随机性和几何的。本文研究了三种具体的方法(a)通过随机漫步对高维分布进行采样，(b)离散集的凸松弛和(c)谱投影。这些技术已经解决了一些基本问题（产生了有效的算法），包括体积计算、凸优化、一些NP-hard离散优化问题的近似算法和分布混合学习。该项目解决了这些技术的范围和效率，并解决了这个过程中基本的开放性问题。其中包括：哪些函数可以通过随机漫步方法有效地采样？体积计算的复杂度是多少？不对称的TSP比对称的TSP更难吗？光谱法的局限性是什么？

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?