Randomized Algorithms: Approximation, Generation, and Counting

1 Mathematical Background.- 1.1 Computational Complexity.- 1.2 Probability.- 1.3 Markov Chains.- 1.4 Graph Theory.- 2 Techniques for Sampling and Approximate Sampling.- 2.1 Introduction.- 2.2 Direct Sampling.- 2.3 Markov Chain Method.- 3 Approximate Counting.- 3.1 Parsimonious Reductions.- 3.2 Counting Directly.- 3.3 Counting and Sampling.- 3.4 The Markov Chain Monte Carlo Method.- 4 Applications: Coupling.- 4.1 Hypergraph Colourings.- 4.2 Sink-Free Graph Orientations and Twice-Sat.- 4.3 Log-Concave Sampling, and the Volume of a Convex Body.- Intermezzo: Path Coupling.- 5 Applications: Path Coupling.- 5.1 Introduction.- 5.2 Twice-Sat Revisited.- 5.3 Sink- and Source-Free Graph Orientations.- 5.4 Totally Edge Cyclic Orientations.- 5.5 Independent Sets: The Conserved Hard-Core Model.- 5.6 Independent Sets: The Non-Conserved Hard-Core Model.- 5.7 Linear Extensions of a Partial Order.- 5.8 Graph Colouring.- 5.9 The Extended Potts Framework.- 5.10 Graph Colouring Revisited.- 6 Directions for Future Work.- 6.1 Breaking Thresholds.- 6.2 Beyond Self-Reducibility.- 6.3 Mixed Methods for Approximate Counting.- 6.4 Faster Reductions from Approximate Counting to Approximate Sampling.- 6.5 Anti-ferromagnetic Models.- 6.6 Log-Concave Sampling via Path Coupling.- Appendices.- A An Application of Dobrushin’s Uniqueness Criterion.- B A Hierarchy of #SAT Restrictions.- B.1 Introduction.- B.2 A Summary of Known Results.- B.2.1 Easy Exact Counting.- B.2.2 Hard Exact Counting.- B.2.3 Easy Approximate Counting.- B.2.4 Hard Approximate Counting.- B.3 Summary and Conclusions.- C Equivalence of Transposition Distance to Spearman’s Footrule.