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. Language: English