The Discrepancy Method: Randomness and Complexity

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.

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.