Organizational Stuff
  • Topic: Counting and Sampling.
  • Organizers: Rad Niazadeh and Nima Anari.
  • Mailing List: algorithmic-toolbox-sp18 at cs
    Send an email to Nima Anari to be added to the mailing list.
  • Usual Date/Time: Fridays starting at 2:00PM (lasting for 2 hours).
  • Usual Place: Gates 463A.
History and Upcoming Talks
  1. First organizational meeting was held on March 16, 2018 at 2:30PM in Gates 463A. Proposed topics were discussed and voted.
  2. Second meeting was held on Wednesday, April 4, 2018 from 2:00PM-4:00PM at Gates 463A. Topics:
    • Equivalence of approximate sampling and counting.
    • Sampling random spanning trees via random walks.
  3. Third meeting will be held on Monday, April 23, 2018 from 3:00PM-5:00PM at Gates 463A. Topics:
    • Markov chain mixing time.
    • Path coupling.
    • Counting graph colorings.
  4. Fourth meeting will be held on Friday, April 27, 2018 from 2:00PM-4:00PM at Gates 400. Topics:
    • Expansion and Markov chain mixing.
    • Basis exchange Markov chain for balanced matroids.
Proposed Topics

Below are some proposed topics/papers. If you have more suggestions please send an email to the organizers (at any point).

Votes were held in the first meeting. The red numbers show how many people did not vote for each topic, and the results are sorted.

  1. 0 (Classic) Approximate sampling, approximate counting, and their equivalence (JS'89).
  2. 0 Sampling random spanning trees via random walks (A'90, B'89, W'96, and possibly more recent and faster methods culminating in S'17).
  3. 0 Sampling graph colorings (V'99, HV'06).
  4. 0 Correlation decay and its application in designing deterministic algorithms for counting matchings (BGKNT’07, GK’08).
  5. 1 The Ising model and approximating its partition function. (LSS'17).
  6. 2 Counting independent sets, computing the independence polynomial (W’06, HSV’17).
  7. 2 Deterministic approximation of permanent, Tutte polynomial, etc. and connections to roots of partition function (B'16, PR'17).
  8. 2 Geometry of polynomials (real stability, etc.) and applications to counting (GS'14, SV'17, AO'17).
  9. 2 Maximum entropy distributions, sampling, counting and optimization (SV’13, BJ’12, AGR’16).
  10. 3 Counting bases of balanced matroids (FM'92).
  11. 5 Approximating the permanent of nonnegative matrices, sampling perfect matchings in bipartite graphs (JSV'04).
  12. 5 Approximating the volume of convex polytopes (KLS'97, LV'17).
  13. 5 (Classic) DNF counting and network unreliability (KLM'89, K'99, K'16).
  14. 5 Mixed Nash equilibria and mixed volumes (MM'94).
  15. 6 Applications in statistical physics and phylogenetic (Steel’s conjecture MS’08 , Ising model).
  16. 9 CNF counting in the Lovasz Local Lemma regime (M'17).