E0 203 · Spectral Algorithms

E0 203January–April 2018

Spectral Algorithms

Department of Computer Science and Automation · Indian Institute of Science

Instructors

Prof. Ambedkar Dukkipati

Prof. Anand Louis

Lectures

Monday and Wednesday, 3:30 – 5:00 PM, CSA 117

Course description

Spectral graph algorithms are very popular in theoretical computer science and machine learning, as they provide polynomial-time approximations to several hard computational problems. This course covers some basic topics in spectral graph theory and algorithms, with applications to network analysis. The course emphasises rigorous analysis of algorithms.

Registration

Course discussions were held on Piazza.

Assignments

Lectures

DateTopic
January 5Organizational meeting
January 13Eigenvalues and eigenvectors of a matrix
January 15Eigenvalues and eigenvectors (contd.)
January 17Spectral radius; the Gershgorin theorem; the first eigenvalue and the maximum degree of a graph
January 22Graph colouring; Wilf's theorem; matrices associated with a graph; properties of the Laplacian
January 24The Laplacian and spectra of simple graphs
January 29The Courant–Fischer and Perron–Frobenius theorems
January 31Symmetric matrices; more spectral properties of adjacency and Laplacian matrices
February 5Cheeger cuts, ratio cuts, normalized cuts and spectral relaxations
February 7Cheeger's inequality and spectral clustering

References