Information

Instructor
Nima Anari (anari@cs.stanford.edu)
Time
Tuesdays and Thursdays 1:30-2:50pm
Location
Wallenberg (Building 160) Room 314
Office Hours
Tuesdays after class and by appointment (Gates 474)

Schedule

The following is a tentative list of topics.

There will be a single evolving document serving the purpose of lecture notes (under construction).

I will attempt to record the lectures, and contingent on having sufficient quality, share the videos.

Tuesday 1/7
Introduction (slides)
Thursday 1/9
Real-rootedness; interlacing; matching polynomial
Tuesday 1/14
Real stability; multivariate matching polynomial; closure properties
Thursday 1/16
DPPs; correlation bounds
Tuesday 1/21
Capacity and approximating the permanent
Thursday 1/23
Hyperbolic polynomials; log-concavity and convex programming;
Tuesday 1/28
No lecture due to MIFODS workshop (no need to study: slides)
Thursday 1/30
Determinant maximization; log-concave polynomials and matroids; entropy approximation
Tuesday 2/4
High-dimensional expanders; random walks; mixing time analysis
Thursday 2/6
Trickle-down of expansion; local-to-global transfer of expansion
Tuesday 2/11
Concentration inequalities
Thursday 2/13
Discrete convexity; gross substitutes; mixing in infinite DPPs
Tuesday 2/18
Beyond log-concavity; fractional log-concavity
Thursday 2/20
Barvinok's method; approximating the permanent of complex matrices
Tuesday 2/25
Cluster expansion
Thursday 2/27
Interlacing families; Ramanujan graphs
Tuesday 3/3
Applications to variants of the traveling salesperson problem
Thursday 3/5
Intro to Hodge theory; volume polynomials
Tuesday 3/10
Student presentations or additional topics
Thursday 3/12
Student presentations or additional topics

Evaluation

There will be three types of evaluation:

  1. Two homework sets (both due by the last day of class)
  2. Overview of 1-2 papers in the form of a short presentation or short writeup
  3. Course project (groups of up to 2), accompanied by in-class presentation

For letter grades, please do either 1+2, or 3.

For CR, please do any of the options 1, 2, or 3.

For suggestions on 2 or 3, you can chat with Nima, or see the following page: (under construction).

References

Under construction.