The Discrepancy Method

Randomness and Complexity

Bernard Chazelle

476 pages, parution le 19/03/2002

Ajouter à une liste

Indisponible

Résumé

The discrepancy method is the glue that binds randomness and complexity. It is the link between discrepancy theory, an area of mathematics concerned with irregularities in distributions, and the seemingly unrelated subject of randomized algorithms. The discrepancy method has been 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 books tells the story of the discrepancy method in a few short independent vignettes. The itinerary includes such topics as communication complexity, rapidly mixing Markov chains, points on a sphere, derandomization, geometric sampling and VC-dimension theory, circuit complexity, and multidimensional searching. The mathematical treatment is thorough and self-contained, with minimal prerequisites. Thus the book should appeal to students as well as researchers in computer science, operations research, pure and applied mathematics, and engineering.

Contents

Preface

1 Combinatorial Discrepancy 1
2 Upper Bound Techniques 33
3 Lower Bound Techniques 125
4 Sampling 161
5 Geometric Searching 195
6 Complexity Lower Bounds 220
7 Convex Hulls and Voronoi Diagrams 273
8 Linear Programming and Extensions 297
9 Pseudorandomness 306
10 Communication Complexity 336
11 Minimum Spanning Trees 366

A Probability Theory 419
B Harmonic Analysis 431
C Convex Geometry 438

Bibliography 443
Index 458

L'auteur - Bernard Chazelle

Bernard Chazelle est professeur à l'université de Princeton, où il occupe la chaire d'informatique Eugene Higgins. Il a également enseigné à l'École normale supérieure d'Ulm, à l'École polytechnique, à l'université Paris-Sud et à l'INRIA. Après avoir étudié le rôle de l'aléa dans la complexité algorithmique, il s'intéresse depuis quelques années aux systèmes dynamiques du monde vivant. Il est titulaire de la chaire d'Informatique et sciences numériques au Collège de France pour l'année 2012-2013.

Autres livres de Bernard Chazelle

L'algorithmique et les sciences

Découvrir tous les livres de Bernard Chazelle

Caractéristiques techniques

	PAPIER
Éditeur(s)	Cambridge University Press
Auteur(s)	Bernard Chazelle
Parution	19/03/2002
Nb. de pages	476
Format	15 x 23
Couverture	Broché
Poids	662g
Intérieur	Noir et Blanc
EAN13	9780521003575
ISBN13	978-0-521-00357-5