Spectral Algorithms

CSC 5160

Site menu:

• Information
• Announcement
• Notes
• Homework
• Project

CSC 5160: Spectral Algorithms

This is a graduate course on algorithm design using spectral techniques. We will study how eigenvalues and eigenvectors of matrices can be used to design and analyze algorithms, from graph partitioning to combinatorial optimization to random walk to coding theory to solving linear equations.

Lecture:	Tuesdays 2:30-6:15, Wen Lan Tang LG 203
Instructor:	Lap Chi Lau
Tutor:	Tsz Chiu Kwok
TA office hour:	Fridays 10:30-11:15, MMW 707

We will cover from the basics to the most recent developments. Below is a list of tentative topics.

• eigenvalues, eigenvectors, Laplacian matrices.
• second eigenvalue, Cheeger's inequality.
• last eigenvalue, maximum cut, independent set.
• more eigenvalues, multi-partitioning.
• spectra of random graphs, planted model.
• random walk.
• pagerank, local graph partitioning.
• expander graphs, zig-zag product.
• coding, expander codes.
• linear equations, iterative method.
• more iterative method, preconditioners.
• electric flow, graph sparsification.
• Laplacian solver.
• multiplicative update, maximum flow.

This course does not have a textbook. We will provide notes. The following is a list of references.

• Course notes by Dan Spielman.
• Spectral graph theory by Fan Chung.
• Algebraic graph theory by Chris Godsil and Gordon Royle.
• a visualization program.

Computer Science and Engineering, The Chinese University of Hong Kong.