Cover; Half-title; Title; Copyright; Dedication; Contents; Preface; 1 Chernoff-Hoeffding Bounds; 2 Applications of the Chernoff-Hoeffding Bounds; 3 Chernoff-Hoeffding Bounds in Dependent Settings; 4 Interlude: Probabilistic Recurrences; 5 Martingales and the Method of Bounded Differences; 6 The Simple Method of Bounded Differences in Action; 7 The Method of Averaged Bounded Differences; 8 The Method of Bounded Variances; 9 Interlude: The Infamous Upper Tail; 10 Isoperimetric Inequalities and Concentration; 11 Talagrand's Isoperimetric Inequality
12 Isoperimetric Inequalities and Concentration via Transportation Cost Inequalities13 Quadratic Transportation Cost and Talagrand's Inequality; 14 Log-Sobolev Inequalities and Concentration; Appendix A Summary of the Most Useful Bounds; Bibliography; Index
Summary
A coherent and unified account of techniques for analyzing the performance of randomized algorithms
