Buch, Englisch, 112 Seiten, Format (B × H): 178 mm x 254 mm, Gewicht: 520 g
Buch, Englisch, 112 Seiten, Format (B × H): 178 mm x 254 mm, Gewicht: 520 g
Reihe: Lectures in Mathematics. ETH Zürich
ISBN: 978-3-7643-6946-0
Verlag: Springer
Zielgruppe
Research
Autoren/Hrsg.
Fachgebiete
- Mathematik | Informatik Mathematik Stochastik Mathematische Statistik
- Naturwissenschaften Physik Angewandte Physik Statistische Physik, Dynamische Systeme
- Mathematik | Informatik EDV | Informatik Informatik
- Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Numerische Mathematik
- Mathematik | Informatik Mathematik Stochastik Wahrscheinlichkeitsrechnung
Weitere Infos & Material
Foreword.- 1 Two good counting algorithms.- 1.1 Spanning trees.- 1.2 Perfect matchings in a planar graph.- 2 #P-completeness.- 2.1 The class #P.- 2.2 A primal #P-complete problem.- 2.3 Computing the permanent is hard on average.- 3 Sampling and counting.- 3.1 Preliminaries.- 3.2 Reducing approximate countingto almost uniform sampling.- 3.3 Markov chains.- 4 Coupling and colourings.- 4.1 Colourings of a low-degree graph.- 4.2 Bounding mixing time using coupling.- 4.3 Path coupling.- 5 Canonical paths and matchings.- 5.1 Matchings in a graph.- 5.2 Canonical paths.- 5.3 Back to matchings.- 5.4 Extensions and further applications.- 5.5 Continuous time.- 6 Volume of a convex body.- 6.1 A few remarks on Markov chainswith continuous state space.- 6.2 Invariant measure of the ball walk.- 6.3 Mixing rate of the ball walk.- 6.4 Proof of the Poincarü inequality (Theorem 6.7).- 6.5 Proofs of the geometric lemmas.- 6.6 Relaxing the curvature condition.- 6.7 Using samples to estimate volume.- 6.8 Appendix: a proof of Corollary 6.8.- 7 Inapproximability.- 7.1 Independent sets in a low degree graph.