The discrepancy method : Randomness and complexity
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...
में बचाया:
| मुख्य लेखक: | |
|---|---|
| स्वरूप: | पुस्तक |
| भाषा: | Undetermined |
| प्रकाशित: |
Cambridge, UK
Cambridge University Press
2000
|
| विषय: | |
| टैग : |
टैग जोड़ें
कोई टैग नहीं, इस रिकॉर्ड को टैग करने वाले पहले व्यक्ति बनें!
|
| Thư viện lưu trữ: | Trung tâm Học liệu Trường Đại học Cần Thơ |
|---|
| सारांश: | 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 |
|---|