Computer Science 287/487

Sampling Algorithms

Fall 2023

Instructor: Daniel Štefankovič
Class: Monday, Wednesday 2:00pm-3:15pm, Harkness 210.
Instructor office hours, ONLINE (Zoom, link on blackboard): Monday 9:00pm-10:00pm, Wednesday 9:00pm-10:00pm.


Textbooks: there is no required textbook; see each section for the recommended reading (mostly online; I will also supply handouts).

Other resources/recommended reading:

• [MR95] Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
• [H02] Finite Markov chains and algorithmic applications, O. Haggstrom, 2002.
• [J03] Counting, sampling and integrating: algorithms and complexity, M. Jerrum, 2003.
• [H16] Perfect Simulation, M. Huber, 2016.
• [MU17] Probability and Computing: Randomized Algorithms and Probabilistic Analysis (2nd ed), M. Mitzenmacher, E. Upfal, 2017.
• [LP17] Markov Chains and Mixing Times, D. Levin, Y. Peres, 2017.

Related courses:

• [Vigoda 2021]
• [Oveis-Gharan 2017]
• [Randal 2014]
• [Daskalakis 2011]
• [Vigoda 2006]
• [Mossel 2006]

Schedule

TOPIC 1: Introduction (3-4 class)

Introduction to counting and sampling.
Concentration inequalities (Chebyshev, Chernoff).
Monte Carlo, permanent Estimator.
Rejection sampling, DNF formulas.
Importance sampling.
Survey of results and open problems.

Reading:

• [MU17] - Sections 1,2,3,4
• [J03] - Section 3.1 and 3.2

TOPIC 2: Complexity theoretic aspects of counting/sampling (3-4 classes)

Exact counting, spanning trees (determinant).
#P-completeness (permanent).
Counting to sampling connection.
Approximate counting (#BIS).

Reading:

• [J03] - Chapter 1 and 2
• M. Dyer, L. Goldberg, C. Greenhill, M. Jerrum. The Relative Complexity of Approximate Counting Problems.

TOPIC 3: Markov chain basics (3-4 classes)

Markov chain, ergodicity. Stationary distribution.
Ergodicity. Total variation distance. Mixing time.
Reversibility. Detailed balance condition.
Relaxation time.
Log Sobolev inequalities, Entropy factorization.

Reading:

• [J03] - Section 3.3
• [LP17] - Chapters 1,2,3,4

TOPIC 4: Coupling (3-4 classes)

Path coupling.
Colorings. Linear extensions. Spanning trees.
Censoring. Coupling for Ising model.

Reading:

• [J03] - Chapter 4
• [LP17] - Chapter 5
• R. Bubley, M. Dyer. Faster Random Generation of Linear Extensions.
• D. Wilson. Mixing times of lozenge tiling and card shuffling Markov chains.
• Y. Peres, P. Winkler. Can Extra Updates Delay Mixing?
• E. Mossel, A. Sly. Exact Thresholds for Ising-Gibbs Samplers on General Graphs.

TOPIC 6: Canonical paths (4-5 classes)

Conductance, canonical paths, lower and upper bounds on mixing time.
Matchings.
Permanent. Annealing.

Reading:

• [J03] - Chapter 5
• M. Jerrum, A. Sinclair. Polynomial-Time Approximation Algorithms for the Ising Model.
• M. Jerrum, A. Sinclair, E. Vigoda. A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Nonnegative Entries.
• I. Bezáková, D. Štefankovič, V. Vazirani, E.Vigoda. Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems.
• D. Štefankovič, S. Vempala, E.Vigoda. Adaptive Simulated Annealing: A Near-Optimal Connection between Sampling and Counting.
• M. Huber. Approximation algorithms for the normalizing constant of Gibbs distributions.

TOPIC 6: Perfect sampling (3-4 classes)

Network unreliability.
Coupling from the past.
LLL based perfect sampling. Network reliability.

Reading:

• [H02] - Chapters 10 and 11.
• R. Moser, G. Tardos. A constructive proof of the general Lovász Local Lemma.
• H. Guo, M. Jerrum, J. Liu. Uniform Sampling Through the Lovász Local Lemma.
• H. Guo, K. He. Tight bounds for popping algorithms.

TOPIC 8: Spectral independence, local-to-global approach (4-5 classes)

Sampling Bases of a Matroid.
Influence matrix.

Reading:

• N. Anari, S. Oveis Gharan, C. Vinzant. Log-Concave Polynomials I: Entropy and a Deterministic Approximation Algorithm for Counting Bases of Matroids.
• N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant. Log-Concave Polynomials II: High-Dimensional Walks and an FPRAS for Counting Bases of a Matroid.
• N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant. Log-Concave Polynomials III: Mason's Ultra-Log-Concavity Conjecture for Independent Sets of Matroids.
• N. Anari, K. Liu, S. Oveis Gharan, C. Vinzant. Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees.
• M. Cryan, H. Guo, G. Mousa. Modified log-Sobolev inequalities for strongly log-concave distributions.
• V. Alev, L. Lau. Improved Analysis of Higher Order Random Walks and Applications.
• N. Anari, K. Liu, S. Oveis Gharan. Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model.
• Z. Chen, K. Liu, E. Vigoda. Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction.
• Z. Chen, A. Galanis, D. Štefankovič, E. Vigoda. Rapid Mixing for Colorings via Spectral Independence.
• W. Feng, H. Guo, Y. Yin, C.Zhang. Rapid mixing from spectral independence beyond the Boolean domain.
• H. Guo, M. Jerrum. Random Cluster Dynamics for the Ising Model is Rapidly Mixing.

TOPIC 9: Tight results (2 classes)

Correlation decay technique for the hard-core model.
Tight hardness result for the hard-core model.

Reading:

• D. Weitz. Counting Independent Sets up to the Tree Threshold.
• A. Sinclair, P. Srivastava, M. Thurley. Approximation Algorithms for Two-State Anti-Ferromagnetic Spin Systems on Bounded Degree Graphs.
• L. Li, P. Lu, Y. Yin. Correlation Decay up to Uniqueness in Spin Systems.
• N. Sun, A. Sly. Counting In Two-Spin Models on d-regular Graphs.
• A. Galanis, D. Štefankovič, E.Vigoda. Inapproximability for Antiferromagnetic Spin Systems in the Tree Nonuniqueness Region.

Grading

The grade for the course is based on the homework (mostly theoretical; there will be 4-6 problem sets) and a small project; there are no exams.

Homework Rules

• Theoretical homework should be typeset (LaTeX preferred) and submitted on gradescope (specific for each assignment). You may work with other people on the theoretical homework, but you must each write up your solutions separately (without any written aid). If you work with other people, indicate who you worked with on your solution.
  
  
• No late homework will be accepted without instructor's permission (a permission must be requested at least 24 hours before the due date).

This course follows The University Policy on Academic Honesty .