CS-455 Topics in Theoretical Computer Science

Spectral Graph Algorithms

Credits: 4
Lecturer: Michael Kapralov
Email: michael.kapralov@epfl.ch
Office: INJ113
Office hours: by appointment
TA: Jakab Tardos
Email: jakab.tardos@epfl.ch
Office hours: TBD
Schedule: Mondays 14-18 in INF119

Short description: The convergence of continuous and discrete methods is a major trend in modern combinatorial optimization. This course will focus on some of the recent algorithmic results in graph processing that crucially rely on spectral techniques to perform graph partitioning, solve linear systems and more. We will start from the basics and build an algorithmic toolbox that relies on deep connections to random walks, electrical networks and metric embeddings, and results in nearly linear time algorithms for several fundamental graph problems.

List of topics (tentative):

Prerequisites: Bachelor courses on algorithms, complexity theory, and discrete mathematics; mathematical maturity.

Grading: The grade will be based on problem sets (60%) and a final (40%).

For more details see the official course book here.