Concentration of Measure for the Analysis of Randomized Algorithms

ISBN-13: 9781107606609 / Angielski / Miękka / 2012 / 214 str.

Devdatt P Dubhashi

Opis

This book presents a coherent and unified account of classical and more advanced techniques for analyzing the performance of randomized algorithms.

Recenzje

Reviews of the hardback: 'This timely book brings together in a comprehensive and accessible form a sophisticated toolkit of powerful techniques for the analysis of randomized algorithms, illustrating their use with a wide array of insightful examples. This book is an invaluable resource for people venturing into this exciting field of contemporary computer science research.' Prabhakar Ragahavan, Yahoo Research

Spis treści

1. Chernoff–Hoeffding bounds; 2. Applying the CH-bounds; 3. CH-bounds with dependencies; 4. Interlude: probabilistic recurrences; 5. Martingales and the MOBD; 6. The MOBD in action; 7. Averaged bounded difference; 8. The method of bounded variances; 9. Interlude: the infamous upper tail; 10. Isoperimetric inequalities and concentration; 11. Talagrand inequality; 12. Transportation cost and concentration; 13. Transportation cost and Talagrand's inequality; 14. Log–Sobolev inequalities; Appendix A. Summary of the most useful bounds.