This is an old revision of the document!

Spectral graph theory and its applications in algorithms

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. Based on the student's interests this can be both a theoretical and practical study. A theoretical study would aim towards understanding recent developments where better (theoretical) algorithms have been given for fundamental problems by the use of spectral methods. A more practical study would instead aim towards implementing some of the algorithms (e.g., clustering) and analyze their performance.

The prerequisite is being comfortable with the basics of graph theory and discrete mathematics; and programming if the practical direction is chosen.