Spectral Techniques in Algorithm Design and Analysis

应用谱技术，利用邻接矩阵或拉普拉斯矩阵的特征值和特征向量来研究组合图的性质已经有很长的历史了。谱图理论的一些关键贡献是发展了扩展图理论，设计了图划分算法，并分析了随机游动的混合时间。这些经典主题在各个领域有不同的应用，被广泛研究并被认为是很好的理解。在过去的十年里，人们对谱图理论的兴趣出现了惊人的复苏。高维展开器、谱稀疏化和高本征值的研究在解决算法和数学中的重大公开问题方面发展了强大的新思想和新技术。在过去的几年里，我和我的学生一直在研究谱图理论和随机游动。我们发现光谱技术可以在以下领域产生重大影响，无论是在设计新算法方面，还是在改进著名算法的数学分析方面。分析马尔可夫链蒙特卡罗算法的谱方法：最近，有几次尝试发展高维扩展器的理论。令人惊讶的是，新的结果被用来证明拟阵展开猜想，这是马尔可夫链蒙特卡罗方法中的一个主要公开问题。我们的目标是发展这种谱方法的理论，以改进其他随机采样算法的分析。除了使用频谱条件的算法的最坏情况分析之外：一些著名的算法的最坏情况分析很差，但在实际应用中被观察到工作得很好。解释这一差距的一种方法是证明实际实例满足一些附加性质，利用这些性质，算法具有可证明的更好的性能。在以前的工作中，我们已经确定了光谱条件，以便为光谱划分和算子缩放提供更好的分析。我们的目标是将这种方法扩展到分析其他著名的算法。网络设计的谱方法：网络设计是计算机科学和运筹学中的一个经典领域，其目标是找到满足特定连通性约束的最小费用子图。图稀疏的新技术表明，控制图的谱性质以控制其组合性质在算法上更加方便。受此启发，我们建议使用这种频谱方法来显著扩展网络设计问题的范围。随机游动和概率方法：最近，在设计有效的算法来寻找通过概率方法证明其存在的对象方面取得了突破，其中新的算法是基于随机游动的。我们计划开发一种频谱方法来分析这些随机行走。一个长期的目标是为Kadison-Singer问题的新的概率方法设计一个有效的算法。

The application of spectral techniques, using eigenvalues and eigenvectors of adjacency or Laplacian matrices, to study combinatorial graph properties has a long history. Some key contributions of spectral graph theory are in developing the theory of expander graphs, in designing graph partitioning algorithms, and in analyzing the mixing time of random walks. These classical topics have diverse applications in various areas, and are extensively studied and considered well understood. The past decade has seen a striking revival of interest in spectral graph theory. The studies of high-dimensional expanders, spectral sparsification, and higher eigenvalues have developed powerful new ideas and techniques in resolving major open problems in algorithms and mathematics. My students and I have been working on spectral graph theory and random walks in the past few years. We have found the following areas where spectral techniques could make significant impact, both in designing new algorithms and in improving mathematical analyses of well-known algorithms. Spectral approach in analyzing Markov chain Monte Carlo algorithms: Recently, there are several attempts to develop a theory for high dimensional expanders. Surprisingly, the new results were used in proving the matroid expansion conjecture, a major open problem in the Markov chain Monte Carlo method. We aim to develop the theory of this spectral approach to improve the analysis of other random sampling algorithms. Beyond worst case analysis of algorithms using spectral conditions: Some well-known algorithms have bad worst case analysis but are observed to work well in practical applications. One approach to explain this gap is to show that practical instances satisfy some additional property, with which the algorithms have provable better performance. In previous work, we have identified spectral conditions to provide better analysis for spectral partitioning and operator scaling. We aim to extend this approach to analyze other well-known algorithms. A spectral approach to network design: Network design is a classical area in computer science and operations research, where the objective is to find a minimum cost subgraph that satisfies certain connectivity constraints. New techniques for graph sparsification showed that it is algorithmically more convenient to control the spectral properties of the graph in order to control its combinatorial properties. Inspired by this, we propose to use this spectral approach to significantly extend the scope for network design problems. Random walks and probabilistic methods: Recently, there are breakthroughs in designing efficient algorithms for finding objects whose existences are proved by probabilistic methods, where the new algorithms are based on random walks. We plan to develop a spectral approach to analyze these random walks. A long term goal is to design an efficient algorithm for the new probabilistic method for the Kadison-Singer problem.