Randomized Algorithms: Approximation, Generation, and Counting

1 Mathematical Background.- 1.1 Computational Complexity.- 1.1.1 Introduction.- 1.1.2 Notation for Asymptotics: ?, ?, and ?.- 1.1.3 Complexity Classes.- 1.1.4 Oracles, Reductions, and Hardness.- 1.1.5 More Complexity Classes.- 1.1.6 Conclusion.- 1.1.7 Some Common Problems in Complexity Theory.- 1.2 Probability.- 1.3 Markov Chains.- 1.4 Graph Theory.- 1.4.1 Tutte-Gröthendieck Polynomial.- 1.4.2 Hypergraphs.- 2 Techniques for Sampling and Approximate Sampling.- 2.1 Introduction.- 2.1.1 Definitions.- 2.2 Direct Sampling.- 2.2.1 Monte Carlo Method: Rejection Sampling.- 2.2.2 Karp-Luby Technique.- 2.3 Markov Chain Method.- 2.3.1 Coupling.- 2.3.1.1 Maximal couplings.- 2.3.2 Dobrushin's Uniqueness Criterion.- 2.3.3 Canonical Paths.- 2.3.4 Conductance.- 2.3.5 Comparison Methods.- 2.3.6 Other Methods.- 2.3.6.1 Poincaré-type inequalities.- 2.3.6.2 Logarithmic Sobolev inequalities.- 2.3.7 Coupling from the Past.- 3 Approximate Counting.- 3.1 Parsimonious Reductions.- 3.2 Counting Directly.- 3.2.1 Direct Sampling.- 3.2.2 Karp-Luby Technique.- 3.3 Counting and Sampling.- 3.4 The Markov Chain Monte Carlo Method.- 4 Applications: Coupling.- 4.1 Hypergraph Colourings.- 4.1.1 Introduction.- 4.1.1.1 Notation and preliminaries.- 4.1.2 Approximate Sampling.- 4.1.2.1 Computing the permutation.- 4.1.2.2 Rapidity of coupling.- 4.1.2.3 Two sufficient conditions.- A condition of k > ?1+?3.- A condition of k > 2?2.- 4.1.3 Almost uniform sampling for k=2?2.- 4.1.3 The Approximation Scheme.- 4.1.4 Conclusions.- 4.2 Sink-Free Graph Orientations and Twice-Sat.- 4.2.1 Introduction.- 4.2.1.1 Notation and preliminaries.- 4.2.1.2 Equivalence of Twice-Sat and SFO.- 4.2.2 Decision and Construction.- 4.2.3 Exact Counting.- 4.2.3.1 Self-reducibility.- 4.2.3.2 Relationship to counting independent sets.- 4.2.3.3 #P-completeness of #SFO.- 4.2.4 Approximate Sampling.- 4.2.5 The Approximation Scheme.- 4.2.6 Conclusions.- 4.3 Log-Concave Sampling, and the Volume of a Convex Body.- 4.3.1 Introduction.- 4.3.2 Background and Preliminaries.- 4.3.2.1 Convex bodies and gauge functions.- 4.3.2.2 Sampling equivalence.- 4.3.2.3 Modifying FK.- 4.3.2.4 Metropolis random walks.- 4.3.2.5 The random walk.- 4.3.2.6 Coupling.- 4.3.2.7 Technical results.- 4.3.3 Analysis of the Random Walk.- 4.3.3.1 Boundedness of the walk.- 4.3.3.2 Bringing the random walks close.- 4.3.3.3 Making the random walks meet.- 4.3.4 Improvements.- 4.3.4.1 A faster simulation of the random walk.- 4.3.4.2 An even faster simulation.- 4.3.5 Conclusions.- Intermezzo: Path Coupling.- 5 Applications: Path Coupling.- 5.1 Introduction.- 5.2 Twice-Sat Revisited.- 5.3 Sink- and Source-Free Graph Orientations.- 5.3.1 Introduction.- 5.3.2 Decision and Construction.- 5.3.3 Exact Counting.- 5.3.3.1 Self-reducibility.- 5.3.3.2 #P-completeness of #SSFO.- 5.3.4 Approximate Counting and Sampling.- 5.4 Totally Edge Cyclic Orientations.- 5.4.1 Approximate Sampling.- 5.5 Independent Sets: The Conserved Hard-Core Model.- 5.5.1 #P-Completeness of Exact Counting.- 5.5.2 Approximate Sampling.- 5.6 Independent Sets: The Non-Conserved Hard-Core Model.- 5.6.1 Approximate Counting.- 5.7 Linear Extensions of a Partial Order.- 5.7.1 Introduction.- 5.7.2 Notation and Preliminaries.- 5.7.3 The Coupling.- 5.7.4 Lower Bounds and Related Chains.- 5.7.5 Conclusions.- 5.8 Graph Colouring.- 5.9 The Extended Potts Framework.- 5.10 Graph Colouring Revisited.- 5.10.1 #P-Completeness.- 5.10.2 Approximate Sampling.- 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.