Book description
Praise for the Second Edition:
"Serious researchers in combinatorics or algorithm design will
wish to read the book in its entirety...the book may also be enjoyed
on a lighter level since the different chapters are largely
independent and so it is possible to pick out gems in one's own area..."
-
Formal Aspects of Computing
This Third Edition of The Probabilistic Method reflects the
most recent developments in the field while maintaining the standard
of excellence that established this book as the leading reference on
probabilistic methods in combinatorics. Maintaining its clear writing
style, illustrative examples, and practical exercises, this new
edition emphasizes methodology, enabling readers to use probabilistic
techniques for solving problems in such fields as theoretical computer
science, mathematics, and statistical physics.
The book begins with a description of tools applied in probabilistic
arguments, including basic techniques that use expectation and
variance as well as the more recent applications of martingales and
correlation inequalities. Next, the authors examine where
probabilistic techniques have been applied successfully, exploring
such topics as discrepancy and random graphs, circuit complexity,
computational geometry, and derandomization of randomized algorithms.
Sections labeled "The Probabilistic Lens" offer additional
insights into the application of the probabilistic approach, and the
appendix has been updated to include methodologies for finding lower
bounds for Large Deviations.
The Third Edition also features:
-
A new chapter on graph property testing, which is a current
topic that incorporates combinatorial, probabilistic, and
algorithmic techniques
-
An elementary approach using probabilistic techniques to the
powerful Szemerédi Regularity Lemma and its applications
-
New sections devoted to percolation and liar games
-
A new chapter that provides a modern treatment of the
Erdös-Rényi phase transition in the Random Graph Process
Written by two leading authorities in the field, The Probabilistic
Method, Third Edition is an ideal reference for researchers in
combinatorics and algorithm design who would like to better understand
the use of probabilistic methods. The book's numerous exercises and
examples also make it an excellent textbook for graduate-level courses
in mathematics and computer science.
NOGA ALON, PhD, is Baumritter Professor of
Mathematics and Computer Science at Tel Aviv University, Israel. A
member of the Israel National Academy of Sciences, Dr. Alon has
written over 400 published papers, mostly in the areas of
combinatorics and theoretical computer science. He is the recipient of
numerous honors in the field, including the Erdös Prize (1989), the
Pólya Prize (2000), the Landau Prize (2005), and the Gödel Prize (2005).
JOEL H. SPENCER, PhD, is Professor of Mathematics and Computer
Science at the Courant Institute of Mathematical Sciences at New York
University and is the cofounder and coeditor of the journal Random
Structures and Algorithms. Dr. Spencer has written over 150 published
articles and is the coauthor of Ramsey Theory, Second Edition,
also published by Wiley.
