The discrepancy method. Randomness and c
โ Chazelle B.
๐ Library
๐
2001
๐ English
โฆ LIBER โฆ
๐
The Discrepancy Method: Randomness and Complexity
โ Scribed by Chazelle B.
- Publisher
- Cambridge University Press
- Year
- 2000
- Tongue
- English
- Leaves
- 491
- Edition
- draft
- Category
- Library
โฌ Acquire This Volume
No coin nor oath required. For personal study only.
โฆ 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
๐ SIMILAR VOLUMES
The Discrepancy Method: Randomness and C
โ Bernard Chazelle
๐ Library
๐
2000
๐ Cambridge University Press
๐ English
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 succi
Randomness and Completeness in Computati
โ Dieter van Melkebeek (auth.)
๐ Library
๐
2000
๐ Springer-Verlag Berlin Heidelberg
๐ English
<p>This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1
Randomness and Completeness in Computati
โ Dieter van Melkebeek (auth.)
๐ Library
๐
2000
๐ Springer-Verlag Berlin Heidelberg
๐ English
<p>This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1
The Discrepancy Method
โ Bernard Chazelle
๐ Library
๐
2002
๐ English
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 succi
Algorithmic Randomness and Complexity
โ Rodney G. Downey, Denis R. Hirschfeldt
๐ Library
๐
2010
๐ Springer
๐ English
<p>Intuitively, a sequence such as 101010101010101010โฆ does not seem random, whereas 101101011101010100โฆ, obtained using coin tosses, does. How can we reconcile this intuition with the fact that both are statistically equally likely? What does it mean to say that an individual mathematical object su