Site menu:

• Information
• Notes
• Project

CS 860: Eigenvalues and Polynomials

Lecture:	Tuesdays and Thursdays, 11:30-12:50, DC 2568.
Instructor:	Lap Chi Lau
Office hours:	Thursdays, 2-3, DC 3120.

This is a research-oriented graduate course. In this course, we will study how eigenvalues and polynomials can be used to design and analyze algorithms for combinatorial problems. Topics include graph expansion, random walks, graph sparsification, interlacing family and real stable polynomials, high dimensional expanders, log-concave polynomials and random sampling. The following is a tentative syllabus.

• Cheeger's inequality and generalizations.
• random walks and mixing time.
• expander graphs, zig-zag product.
• spectral sparsification, random sampling, barrier function.
• spectral rounding, network and experimental design.
• method of interlacing family, restricted invertibility.
• real stable polynomials.
• Ramanujan graphs, matching polynomials.
• Weaver's conjecture, multivariate barrier function.
• strongly Rayleigh distribution, thin tree.
• Gurvits' machinery.
• high dimensional expanders.
• higher-order random walks, matroid expansion conjecture.
• spectral independence, completely log-concave polynomials.
• entropic independence, fractionally log-concave polynomials.
• locally testable codes?

References: Notes will be provided. See my previous notes on CS 860 for some topics, but this is a major revision of the previous course. See also the project page for further references. Below are some similar courses in other universities for your references.

• Spectral Graph Theory, by Dan Spielman.
• Polynomial Paradigm in Algorithm Design, by Shayan Oveis Gharan.
• Recent Developments in Approximation Algorithms, by Shayan Oveis Gharan.

CS, Waterloo.