Nima Anari (
Tuesdays and Thursdays 1:30-2:50pm
Wallenberg (Building 160) Room 314
Office Hours
Tuesdays after class and by appointment (Gates 474)


The following is a tentative list of topics.

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
Determinantal distributions; 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; entropy approximation
Tuesday 2/4
Introduction to approximate counting and sampling
Thursday 2/6
High-dimensional random walks; mixing time analysis
Tuesday 2/11
Localt-to-global analysis of f-divergence
Thursday 2/13
Poincaré and modified log-Sobolev inequalities
Tuesday 2/18
Certifying log-concavity of polynomials; matroids
Thursday 2/20
Exchange properties; tight analysis of random walks
Tuesday 2/25
Discrete convexity; Plücker relations; gross substitutes
Thursday 2/27
Fractional log-concavity; intro to Barvinok's method
Tuesday 3/3
Barvinok's method and applications to approximating the permanent
Thursday 3/5
Bounding the roots; intro to interlacing families of polynomials
Tuesday 3/10
Zoom Q&A; notes on interlacing families
Thursday 3/12
Zoom Q&A


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.