Grant: Discovery Grants Program - Individual
University of Waterloo
$43,000.00
Linear Algebraic Techniques in Algorithmic Graph Theory
EF 2016-17
Résumé
Algorithms for fundamental graph problems are important tools in computer science and engineering. Extensive research has been done in the past decades to develop efficient algorithms, most of them based on combinatorial techniques. In recent years, new linear algebraic techniques have been developed to make surprising and significant progress in these fundamental problems. My previous research develops linear algebraic techniques to design both better approximation algorithms and faster exact algorithms for graph problems. I plan to continue this line of ongoing research and have identified three promising directions to investigate.
Spectral graph theory: The application of spectral techniques to study combinatorial graph properties has a long history. The classical result relates the second eigenvalue to the edge expansion of the graph, and it has been used to develop efficient algorithms for graph partitioning problems and to analyze the mixing time of random walks. Recently, there have been exciting new results relating other eigenvalues to combinatorial graph properties. This new connection opens up ways to do better analysis of existing algorithms, to design better approximation algorithms and to design faster algorithms for various graph problems. I believe that this approach will bring new insights into some outstanding open problems including the small-set expansion conjecture, the bipartite matching problem, and the log-rank conjecture.
Random walks: Random walks are simple stochastic processes on graphs that have a wide range of algorithmic applications. One classical application of random walks is in designing random sampling algorithms. Recently, random walks have been used to design sublinear time graph algorithms. I plan to do a systematic study of the random walks method, to design exact and approximation algorithms and to prove hardness of approximation results. Also, with our new knowledge about random walks and graph expansion, I would like to revisit the outstanding open problems in random sampling, including the matroid expansion conjecture and the mixing time of the Glauber dynamics for graph coloring.
Linear algebraic algorithms: Recently, there has been significant progress in designing fast algorithms for fundamental graph problems using linear algebraic algorithms. A major open problem in this area is to design fast algebraic algorithms for weighted problems. I also plan to develop this approach to solve additional graph problems and linear algebraic problems, and to study the interplay between graph theory and linear algebra.
I believe that achieving the goals in this proposal would have major impacts in the theory of computing, as well as in other areas such as machine learning, applied probability, and symbolic computation. I also expect to have significant contributions to the training of HQPs by acquiring these emerging techniques with my students.
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-2015-04318
Name nom
Lau, LapChi
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheri
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2015
Award amount
43000
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
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Linear Algebraic Techniques in Algorithmic Graph Theory
Keyword
NSERC
Application summary
Algorithms for fundamental graph problems are important tools in computer science and engineering. Extensive research has been done in the past decades to develop efficient algorithms, most of them based on combinatorial techniques. In recent years, new linear algebraic techniques have been developed to make surprising and significant progress in these fundamental problems. My previous research develops linear algebraic techniques to design both better approximation algorithms and faster exact algorithms for graph problems. I plan to continue this line of ongoing research and have identified three promising directions to investigate.
Spectral graph theory: The application of spectral techniques to study combinatorial graph properties has a long history. The classical result relates the second eigenvalue to the edge expansion of the graph, and it has been used to develop efficient algorithms for graph partitioning problems and to analyze the mixing time of random walks. Recently, there have been exciting new results relating other eigenvalues to combinatorial graph properties. This new connection opens up ways to do better analysis of existing algorithms, to design better approximation algorithms and to design faster algorithms for various graph problems. I believe that this approach will bring new insights into some outstanding open problems including the small-set expansion conjecture, the bipartite matching problem, and the log-rank conjecture.
Random walks: Random walks are simple stochastic processes on graphs that have a wide range of algorithmic applications. One classical application of random walks is in designing random sampling algorithms. Recently, random walks have been used to design sublinear time graph algorithms. I plan to do a systematic study of the random walks method, to design exact and approximation algorithms and to prove hardness of approximation results. Also, with our new knowledge about random walks and graph expansion, I would like to revisit the outstanding open problems in random sampling, including the matroid expansion conjecture and the mixing time of the Glauber dynamics for graph coloring.
Linear algebraic algorithms: Recently, there has been significant progress in designing fast algorithms for fundamental graph problems using linear algebraic algorithms. A major open problem in this area is to design fast algebraic algorithms for weighted problems. I also plan to develop this approach to solve additional graph problems and linear algebraic problems, and to study the interplay between graph theory and linear algebra.
I believe that achieving the goals in this proposal would have major impacts in the theory of computing, as well as in other areas such as machine learning, applied probability, and symbolic computation. I also expect to have significant contributions to the training of HQPs by acquiring these emerging techniques with my students.