My Library

University LibraryCatalogue

Limit search to items available for borrowing or consultation
Result Page: Previous Next
Can't find that book? Try BONUS+
Look for full text

Search Discovery

Search CARM Centre Catalogue

Search Trove

Add record to RefWorks

Cover Art
Author Chazelle, B. (Bernard)

Title The discrepancy method : randomness and complexity / Bernard Chazelle.

Published Cambridge : Cambridge University Press, 2000.


Location Call No. Status
Physical description xvii, 463 pages : illustrations ; 24 cm
Bibliography Includes bibliographical references (pages 443-457) and index.
Summary 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 short 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.
Subject Irregularities of distribution (Number theory)
Random variables.
Computational complexity.
ISBN 0521770939 £40.00