Randomized Algorithms: Approximation, Generation, and Counting

Randomized Algorithms discusses two problems of fine pedigree: counting and generation, both of which are of fundamental importance to discrete mathematics and probability. When asking questions like "How many are there?" and "What does it look like on average?" of families of combinatorial structures, answers are often difficult to find -- we can be blocked by seemingly intractable algorithms. Randomized Algorithms shows how to get around the problem of intractability with the Markov chain Monte Carlo method, as well as highlighting the method's natural limits. It uses the technique of coupling before introducing "path coupling" a new technique which radically simplifies and improves upon previous methods in the area.

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.