The Discrepancy Method: Randomness and Complexity (Paperback) (ISBN-13: 9780521003575)

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.

Author: Bernard Chazelle
ISBN-10: 0521003571
ISBN-13: 9780521003575
Publisher: Cambridge University Press
Language: English
Published: 01/14/2002
Pages: 494
Format: Paperback
Weight: 1.43lbs
Size: 8.22h x 6.98w x 0.99d

Review Citation(s):
Choice 12/01/2002 pg. 664