The Discrepancy Method: Randomness and Complexity
Book information
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. More information can be found on the book's home page at http://www.cs.princeton.edu/~chazelle/book.html
Similar books
Advances in Discrete and Computational Geometry
1999 · DJVU
The discrepancy method. Randomness and complexity
2001 · PDF
Cosmical Electrodynamics, 2nd Ed. (International Series of Monographs on Physics)
1963 · DJVU
Theory of Knowledge: An Introduction
1976 · DJVU
Introduction to Stochastic Processes with Special Reference to Methods and Applications
DJVU
Dynamical Theory of Crystal Lattices (The International series of monographs on physics)
1998 · DJVU
Communism and China: Ideology in Flux
1970 · DJVU
American Piety: The Nature of Religious Commitment (Patterns of Religious Commitment)
1970 · DJVU