Grant: Discovery Grants Program - Individual
University of Waterloo
$64,000.00
Spectral Techniques in Algorithm Design and Analysis
EF 2021-22
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2020-04385
Name nom
Lau, Lap Chi
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2021
Competition year année de concours
2020
Award amount
64000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Installment
inst:2
Partie
1
Nb partie
5
Application title
Spectral Techniques in Algorithm Design and Analysis
Keyword
NSERC
Application summary
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.