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 toolkit from the Chernoff-Hoeffding 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 Chernoff-Hoeffding bounds in dependent settings.
The authors emphasise 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.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!