The Discrepancy Method: Randomness and Complexity - Softcover

Chazelle, Bernard

Softcover

ISBN 10: 0521003571 ISBN 13: 9780521003575

Publisher: Cambridge University Press, 2002

Synopsis

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.

About this title

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.

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

Edition details

• Publisher: Cambridge University Press
• Publication date: 2002
• Language: English
• ISBN 10: 0521003571
• ISBN 13: 9780521003575
• Binding: Paperback
• Number of pages: 494