AF: Small: Fundamental Algorithms based on Convex Geometry and Spectral Methods

这个项目使用凸几何、谱分析和复杂性的工具来解决算法理论中的基本开放问题。这项研究还将为函数分析和概率中的核心问题提供算法洞察力。所解决的问题是基本性质的，源自许多领域，包括抽样、优化(离散和连续)、机器学习和数据挖掘。随着高维数据在重要应用领域的丰富，迫切需要有效的工具来处理这些数据，本项目解决了这种需求产生的最基本的问题。在这些问题上的进展肯定会解开深层的数学结构，并产生新的分析工具。随着算法领域的不断扩展(其影响范围远远超出了计算机科学)，这些工具将在形成算法理论方面发挥重要作用。PI目前担任算法和随机性中心的主任，该中心成立于2006年，前提是接触科学家和工程师，并确定可能在计算复杂性理论中发挥基础作用的问题和想法。研究结果构成了本科生和研究生课程的基础，并提供了在线材料。该项目有四个重点主题：(1)张量优化的复杂性。是否存在计算r-重张量的谱范数的多项式时间算法？(2)仿射不变算法。线性规划能在强多项式时间内求解吗？什么是主成分分析的自然仿射不变和噪声容忍版本？(3)高维分布抽样的复杂性，包括上界和下界。哪类非凸体可以有效地采样(优化、积分)？是否存在对最短格子向量的多项式时间优于指数逼近？(4)高维函数的可学性。两个半空间的交集可以通过PAC学习吗？在高斯分布下，可以学习多项式数目的半空间的交集吗？

This project addresses fundamental open problems in the theory of algorithms using tools from convex geometry, spectral analysis and complexity. The research will also provide algorithmic insights into central questions in functional analysis and probability. The problems tackled are of a basic nature, and originate from many areas, including sampling, optimization (both discrete and continuous), machine learning and data mining. With the abundance of high-dimensional data in important application areas, the need for efficient tools to handle such data is pressing and this project addresses the most basic questions arising from this need. Progress on these problems is sure to unravel deep mathematical structure and yield new analytical tools. As the field of algorithms continues to expand (and extends its reach far beyond computer science), such tools will play an important role in forming a theory of algorithms. The PI currently serves as the director of the Algorithms and Randomness Center, founded in 2006 on the premise of outreach to scientists and engineers and to identify problems and ideas that could play a fundamental role in computational complexity theory. The research results form the basis of courses at both the undergraduate and graduate level with materials available online.The project has four focus topics: (1) Complexity of tensor optimization. Does there exist a polynomial-time algorithm for computing the spectral norm of an r-fold tensor? (2) Affine-invariant algorithms. Can linear programs be solved in strongly polynomial time? What is a natural affine-invariant and noise-tolerant version of principal components analysis? (3) Complexity of sampling high-dimensional distributions, both upper and lower bounds. What classes of nonconvex bodies can be sampled (optimized, integrated over) efficiently? Do there exist polynomial-time better-than-exponential approximations to the shortest lattice vector? (4) Learnability of high-dimensional functions. Can the intersection of two halfspaces be PAC-learned? Can the intersection of a polynomial number of halfspaces be learned under a Gaussian distribution?