Spectral Techniques in Algorithm Design and Analysis

算法设计和分析中的谱技术

• 批准号: RGPIN-2020-04385
• 负责人: Lau, LapChi
• 金额: $ 4.66万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750210
• 关键词: Spectral; Techniques; Algorithm; Design; Analysis

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.

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