Concentration of Measure for the Analysis of Randomized Algorithms

by Devdatt P. Dubhashi, Alessandro Panconesi

Randomized algorithms have become a central part of the algorithms curriculum based on their increasingly widespread use in modern applications. This book presents a coherent and unified treatment of probabilistic techniques for obtaining high- probability estimates on the performance of randomized algorithms. It covers the basic tool kit from the Chernoff-Hoeffding (CH) bounds to more sophisticated techniques like Martingales and isoperimetric inequalities, as well as some recent developments like Talagrand's inequality, transportation cost inequalities, and log-Sobolev inequalities. Along the way, variations on the basic theme are examined, such as CH bounds in dependent settings. The authors emphasize comparative study of the different methods, highlighting respective strengths and weaknesses in concrete example applications. The exposition is tailored to discrete settings sufficient for the analysis of algorithms, avoiding unnecessary measure-theoretic details, thus making the book accessible to computer scientists as well as probabilists and discrete mathematicians.

Genres: Computer Science

214 pages, Paperback

First published June 15, 2009

Reviews

[Thore Husfeldt · Rating 5 out of 5]

Splendidly written, crisp, insightful, ambitious, and highly polished.

[Altug Karakurt · Rating 1 out of 5]

TL;DR This is THE worst textbook I have ever laid eyes on.

We studied this book as a group of 7 graduate electrical engineering students, so I'm pretty sure this is not a "oh it was too advanced, it went over your head" kind of bad experiences.

The first chapter is great. Concise, to-the-point and intuitive. I liked the flow of the text a lot and I was looking forward to the following chapters. After this point everything went downhill.

Second chapter was not horrible. The examples were a little too detailed and they took some work to understand. More importantly, most of the intermediate (and sometimes crucial) steps are either skipped or left to the reader without any hints, etc. Exercises are beneficial only when they serve as repetition or extension of a known concept, not when they are employed for the first time.

Third chapter was just a joke. There are typos in the THEOREM statements. Not the derivation, but the actual result. It was obvious that they stopped caring at this point. Some examples contain symbols and functions that are not defined. This is because they are copied from various papers and to understand what the hell is going on, you have to google the problem and try to find a match that also appears in the references of the book and read from there. Most of our time was spent on trying to understand "what the hell does he mean?" rather than thinking about the mathematical arguments.

Such a rich and interesting topic couldn't be butchered worse than this. How a textbook has so many typos, missing notation and blatantly copy-pasted examples is beyond me. Do yourself a favor and look for an alternative source.