Spectral Techniques in Algorithm Design and 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.