Spectral Methods in Computer Science and Combinatorics

Instructor: 

Semester: 

  • 2019 Spring/Summer (Jan - May)

Description: Spectral methods (use of eigenvalue/singular value
decomposition) have come extremely handy both in practice and theory
(improved algorithms in partitioning, sparsification etc  as well as
robust analyses of existing theorems in combinatorics). In this
course, we will explore some of these ideas outlining the fundamental
concepts underlying them.

References:
1. Dan Spielman, Spectral Graph Theory, Course at Yale University, Spring 2018
2. Ravi Kannan and Santosh Vempala, Spectral Algorithms,
3. Yuval Filmus, Spectral methods in extremal combinatorics, PhD
Thesis, Toronto University
4. Godsil and Meagher, Erdős-Ko-Rado Theorems: Algebraic Approaches