The Probabilistic Method

by Noga Alon, Paul Erdős, Joel H. Spencer

One of the most powerful and popular tools used in combinatorics is the probabilistic method. Describes current algorithmic techniques, applying both the classical method and the modern tools it uses. Along with a detailed description of the techniques used in probabilistic arguments, it includes basic methods which utilize expectation and variance plus recent applications of martingales and correlation inequalities. Examines discrepancy and random graphs and covers such topics as theoretical computer science, computational geometry, derandomization of randomized algorithms and more. A study of various topics using successful probabilistic techniques is included along with an Open Problems Appendix by Paul Erdös, the founder of the probabilistic method.

Genres: Mathematics, Technical, Computer Science, Textbooks

Hardcover

First published December 2, 1991

Reviews

[Hlopa · Rating 3 out of 5]

a little bit random for my liking. but, well, what should i expect from a book about probability :)

[Harris]

This has been one of the most challenging texts I've encountered and certainly one of the least self-contained. The method is brilliant and enchanting and when I was able to make sense of things it was very rewarding, but I definitely lacked the background in probability and the effort to remediate that.

[Matthew Zhang · Rating 4 out of 5]

Insane exercises