Skip to content

Concentration of Measure for the Analysis of Randomized Algorithms

Spend $50 to get a free movie!

ISBN-10: 0521884276

ISBN-13: 9780521884273

Edition: 2009

Authors: Devdatt P. Dubhashi, Alessandro Panconesi

List price: $218.95
Blue ribbon 30 day, 100% satisfaction guarantee!
Out of stock
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Customers also bought

Book details

List price: $218.95
Copyright year: 2009
Publisher: Cambridge University Press
Publication date: 6/15/2009
Binding: Hardcover
Pages: 214
Size: 6.00" wide x 9.00" long x 0.75" tall
Weight: 0.990
Language: English

Devdatt Dubhashi is Professor in the Department of Computer Science and Engineering at Chalmers University, Sweden. He earned a Ph.D. in computer science from Cornell University and held positions at the Max-Planck-Institute for Computer Science in Saarbruecken, BRICS, the University of Aarhus, and IIT Delhi. Dubhashi has published widely at international conferences and in journals, including many special issues dedicated to best contributions. His research interests span the range from combinatorics, to probabilistic analysis of algorithms, and to, more recently, computational systems biology and distributed information systems such as the Web.

Alessandro Panconesi is Professor of Computer Science at Sapienza University of Rome. He earned a Ph.D. in computer science from Cornell University and is the recipient of the 1992 ACM Danny Lewin Award. Panconesi has published more than 50 papers in international journals and selective conference proceedings and he is the associate editor of the Journal of Discrete Algorithms and the director of BiCi, the Bertinoro International Center of Informatics. His research spans areas of algorithmic research as diverse as randomized algorithms, distributed computing, complexity theory, experimental algorithmics, wireless networking and Web information retrieval.

Preface
Chernoff-Hoeffding Bounds
What Is "Concentration of Measure"?
The Binomial Distribution
The Chernoff Bound
Heterogeneous Variables
The Hoeffding Extension
Useful Forms of the Bound
A Variance Bound
Pointers to the Literature
Problems
Applications of the Chernoff-Hoeffding Bounds
Probabilistic Amplification
Load Balancing
Skip Lists
Quicksort
Low-Distortion Embeddings
Pointers to the Literature
Problems
Chernoff-Hoeffding Bounds in Dependent Settings
Negative Dependence
Local Dependence
Janson's Inequality
Limited Independence
Markov Dependence
Pointers to the Literature
Problems
Interlude: Probabilistic Recurrences
Problems
Martingales and the Method of Bounded Differences
Review of Conditional Probabilities and Expectations
Martingales and Azuma's Inequality
Generalising Martingales and Azuma's Inequality
The Method of Bounded Differences
Pointers to the Literature
Problems
The Simple Method of Bounded Differences in Action
Chernoff-Hoeffding Revisited
Stochastic Optimisation: Bin Packing
Balls and Bins
Distributed Edge Colouring: Take 1
Models for the Web Graph
Game Theory and Blackwell's Approachability Theorem
Pointers to the Literature
Problems
The Method of Averaged Bounded Differences
Hypergeometric Distribution
Occupancy in Balls and Bins
Stochastic Optimisation: Travelling Salesman Problem
Coupling
Handling Rare Bad Events
Quicksort
Pointers to the Literature
Problems
The Method of Bounded Variances
A Variance Bound for Martingale Sequences
Applications
Pointers to the Literature
Problems
Interlude: The Infamous Upper Tail
Motivation: Non-Lipschitz Functions
Concentration of Multivariate Polynomials
The Deletion Method
Problems
Isoperimetric Inequalities and Concentration
Isoperimetric Inequalities
Isoperimetry and Concentration
The Hamming Cube
Martingales and Isoperimetric Inequalities
Pointers to the Literature
Problems
Talagrand's Isoperimetric Inequality
Statement of the Inequality
The Method of Non-Uniformly Bounded Differences
Certifiable Functions
Pointers to the Literature
Problems
Isoperimetric Inequalities and Concentration via Transportation Cost Inequalities
Distance between Probability Distributions
Transportation Cost Inequalities Imply Isoperimetric Inequalities and Concentration
Transportation Cost Inequality in Product Spaces with the Hamming Distance
An Extension to Non-Product Measures
Pointers to the Literature
Problems
Quadratic Transportation Cost and Talagrand's Inequality
Introduction
Review and Road Map
An L<sub>2</sub> (Pseudo)-Metric on Distributions
Quadratic Transportation Cost
Talagrand's Inequality via Quadratic Transportation Cost
Extension to Dependent Processes
Pointers to the Literature
Problems
Log-Sobolev Inequalities and Concentration
Introduction
A Discrete Log-Sobolev Inequality on the Hamming Cube
Tensorisation
Modified Log-Sobolev Inequalities in Product Spaces
The Method of Bounded Differences Revisited
Self-Bounding Functions
Talagrand's Inequality Revisited
Pointers to the Literature
Problems
Summary of the Most Useful Bounds
Chernoff-Hoeffding Bounds
Bounds for Well-Behaved Functions
Bibliography
Index