Contact: Ola Svensson
Room: BC128
Tel: 31204
Email: ola [dot] svensson [at] epfl [dot] ch
Spectral graph theory is a rich and powerful theory that relates various graph properties with the eigenvalues and eigenvectors of matrices associated to the graph, such as its adjacency matrix.
One of the most famous results is Cheeger's inequality that relates the expansion of a graph with the second largest eigenvalue of its adjacency matrix. In addition to being an interesting theoretical result, Cheeger's inequality has found numerous algorithmic applications in clustering, image analysis, etc..
After reviewing the basics of spectral graph theory, the aim of this project is to understand its various algorithmic applications in theory. The study would aim towards understanding recent developments where better (theoretical) algorithms have been given for fundamental problems by the use of spectral methods (often combined with the use of semidefinite programs).
The prerequisite is being comfortable with the basics of graph theory and discrete mathematics.