Counting and Sampling 2020

Reading group that covers efficient approximate counting and sampling algorithms. 

We largely follow Shayan Oveis Gharan’s lecture notes available on this link. Yury Polyanskiy (MIT) has also kindly agreed to teach several lectures on Markov Chains and techniques for analyzing their mixing time. He will base his lectures on his lecture notes (Lectures 10 and on ward) that are available here.  (This roughly corresponds to Lectures 3-10 of Shayan’s course.)

 

SCHEDULE

  • Mondays  16:15- 18:00 on Zoom 
  • Fridays 11:15  – 13:00 on Zoom

EMAILING LIST FOR ANNOUNCEMENTS

To receive announcements related to this reading group and links to the live sessions, please send an email to [email protected]

 

COMMENTS AND VIDEOS

  • Lecture 1 basically followed the lecture notes of Lecture 1 from Shayan’s course. Sinclair also has a very nice example explaining the technique we used to reduce sampling to counting. It is about volume approximation, see Section 1.2.2 of this pdf. Credits to Nicolas Flammarion for sharing this!
  • Video of Lecture 2 “DNF Counting and Karger’s Algorithm for Network Reliability” available here.
  • Video of Lecture 3 “Markov Chains Intro and Examples” available here. Notes are available here. (See Lecture 10.)
  • Video of Lecture 4 “Bounding mixing time via coupling” available here. For notes, see Lecture 11 in Yury’s notes and Lecture 5 in Shayan’s notes.
  • Video of Lecture 5 “Lower bounds on mixing time via Cheeger bottlenecks” available here.  For notes, see Lecture 12 in Yury’s notes. 
  • Video of Lecture 6 “Path coupling” available here. For notes, see Lecture 13 in Yury’s notes.
  • Video of Lecture 7-8 “Eigenvalues and Spectral Gap” available here. For notes, see Lectures 14 and 15 in Yury’s notes.
  • Video of Lecture 9 “Comparison of Markov Chains. All or Nothing FPRAS theorem” available here. For notes, see Lecture 16 in Yury’s notes and Lecture 8 in Shayan’s notes.
  • Video of Lecture 10 “Sampling non-perfect matchings” available here. For notes, see Lecture 9 in Shayan’s notes. 
  • Video of Lecture 11 “Sampling perfect matchings” available here
  • Videos of Lecture 12 available: Part that finishes last lecture on “Perfect Matchings”  here and the introduction to “Weitz algorithm for independent sets” here.
  • Video of Lecture 13 “Weitz algorithm for counting independent sets” available here.
  • Video of Lecture 14 “Sly’s hardness for counting independent sets” available here.
  • Video of Lecture 15 “Barvinok’s Polynomial Method, Approximating Permanent” available here.
  • Video of Lecture 16 “Barvinok’s Method: Approximating the Matching Polynomial” available here.
  • Video of Lecture 17 “Estimating coefficients of the matching polynomial” available here.
  • Video of Lecture 18 “Zeros and approximation of the partition function of the ferromagnetic Ising model” available here.
  • Video of Lecture 19 “Gurvits’s Technique: Deterministic ALG for Permanent” available here.
  • Video of Lecture 20 “Fast mixing of Glauber dynamics for hardcore model up to Weitz threshold” available here.