The Discrepancy Method: Randomness and Complexity [Paperback]

Bernard Chazelle (Author)

Book Description

ISBN-10: 0521003571 | ISBN-13: 978-0521003575 | Publication Date: January 14, 2002

The discrepancy method has produced the most fruitful line of attack on a pivotal computer science question: What is the computational power of random bits? It has also played a major role in recent developments in complexity theory. This book tells the story of the discrepancy method in a few succinct independent vignettes. The chapters explore such topics as communication complexity, pseudo-randomness, rapidly mixing Markov chains, points on a sphere, derandomization, convex hulls and Voronoi diagrams, linear programming, geometric sampling and VC-dimension theory, minimum spanning trees, circuit complexity, and multidimensional searching. The mathematical treatment is thorough and self-contained, with minimal prerequisites. More information can be found on the book's home page at http://www.cs.princeton.edu/~chazelle/book.html.

Editorial Reviews

Review

"Chazelle writes well, treats the reader generously, and works passionately to find the common threads in a plethora of important, late-breaking developments at the crossroads of mathematics and computer science. Both as personal testament and crafted exposition, this invitation into ongoing research reads with the feel of an intimate audience with an enthusiastic leading expert. Upper division undergraduates through professionals." Choice

Book Description

Randomization is one of the great resources in algorithm design and also one of its great mysteries. Although randomization seems to provide algorithms with more power, there is no proof that it is indeed the case. This book examines the discrepancy method, which may be the 'missing link' between randomness and complexity. The text discusses a selection of important topics illustrating the fruitfulness of this link. Several of the most exciting recent results in algorithms and complexity are covered, such as communication complexity, pseudo-randomness, rapidly mixing Markov chains, and multidimensional searching. With minimal pre-requisites, this book should appeal to students as well as researchers in computer science, operations research, pure and applied mathematics, and engineering.

Product Details

• Paperback: 494 pages
• Publisher: Cambridge University Press (January 14, 2002)
• Language: English
• ISBN-10: 0521003571
• ISBN-13: 978-0521003575
• Product Dimensions: 9.2 x 6.3 x 1.2 inches
• Shipping Weight: 1.8 pounds (View shipping rates and policies)
• Average Customer Review: 5.0 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #617,506 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

4 of 5 people found the following review helpful:

5.0 out of 5 stars An unusual mix of topics, fresh perspective, June 6, 2002

By A Customer

This review is from: The Discrepancy Method: Randomness and Complexity (Paperback)

The title seems to be a play on the "Probabilistic Method,"
a better-known cousin of the Discrepancy Method. The book
covers an unusual mix of topics, and is very well-written.

4 of 6 people found the following review helpful:

5.0 out of 5 stars One of a kind, January 16, 2004

By A Customer

This review is from: The Discrepancy Method: Randomness and Complexity (Paperback)

Deep math meets computer science over
a hugely diverse range of topics:
an amazing book!