Information

Schedule

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:

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.