Site menu:

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.

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.