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?