01441nam a2200217Ia 4500 CTU_166459 210402s9999 xx 000 0 und d 82.22 512.7 C513 Chazelle, B. The discrepancy method : Randomness and complexity Bernard Chazelle Cambridge, UK Cambridge University Press 2000 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 Irregularities of distribution (Number theory),Random variables,Computational complexity,Lý thuyết số,Ngẫu biến,Tính toán ngẫu biến Qhieu Trung tâm Học liệu Trường Đại học Cần Thơ