ENGLISH

The Discrepancy Method: Randomness and Complexity

By Bernard Chazelle

Book information

Publisher
Cambridge University Press
Year
2000
ISBN
0521770939, 9780521770934
Open Library ID
OL7752882M
Language
english
Format
DJVU
Filesize
7 MB (6976795 bytes)
Pages
481\481
DPI
300
Time added
2011-01-08 23:22:23

Description

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.

Similar books