The Discrepancy Method

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.