AF: Small: Spectral analysis, spectral algorithms, and beyond

从机器学习到科学计算，从图形到数据挖掘，从协同过滤到VLSI设计，光谱算法和频谱分析构成了一些最高效和最有效的技术的基础。它们在组合优化中也扮演着重要的角色，它们被用于图划分和约束满足的算法。尽管光谱技术显然很有用，而且对它们的分析投入了大量的努力，但我们对它们进行严格推理的能力仍然非常有限。这个项目致力于发展以算法为中心的光谱分析理论，它利用了当代数学的工具，并受到实验证据的启发，到目前为止，还没有一个令人满意的理论解释。该项目还从计算复杂性的角度讨论了谱方法的相对能力。这涉及到研究仅使用特征值和特征向量的信息不能完成的事情，以及通过将谱分析与经典的组合方法相结合可以获得的结果，例如图流的计算。

TITLE: Spectral analysis, spectral algorithms, and beyond Spectral algorithms and spectral analysis form the basis for some of the most efficient and effective techniques in areas ranging from machine learning to scientific computing, from graphics to data mining, and from collaborative filtering to VLSI design. They also play a prominent role in combinatorial optimization, where they are used in algorithms for graph partitioning and constraint satisfaction. Despite the apparent utility of spectral techniques and the intense effort devoted to their analysis, our ability to reason about them rigorously is still very limited. This project addresses the development of an algorithmically-centered theory of spectral analysis which draws upon tools from contemporary mathematics, and is inspired by experimental evidence which has, so far, eluded a satisfactory theoretical explanation. The project also addresses the relative power of spectral methods from the viewpoint of computational complexity.This involves the both the study of what cannot be done using only information about eigenvalues and eigenvectors, as well as what can be achieved by combining spectral analysis with classical combinatorial approaches, like computation of graph flows.