Bernard Chazelle

The discrepancy method is the glue that binds randomness and complexity. It is the bridge between randomized computation and discrepancy theory, the area of mathematics concerned with irregularities in distributions. The discrepancy method has played a major role in complexity theory; in particular, it has caused a mini-revolution of sorts in computational geometry. This book tells the story of the discrepancy method in a few short independent vignettes. It is a varied tale which includes such topics as communication complexity, pseudo-randomness, rapidly mixing Markov chains, points on the sphere and modular forms, derandomization, convex hulls, Voronoi diagrams, linear programming and extensions, geometric sampling, VC-dimension theory, minimum spanning trees, linear circuit complexity, and multidimensional searching. The mathematical treatment is thorough and self-contained. In particular, background material in discrepancy theory is supplied as needed. Thus the book should appeal to students and researchers in computer science, operations research, pure and applied mathematics, and engineering.

Randomness and Complexity

The Discrepancy Method

Suite à une explosion de résultats surprenants en informatique théorique, une idée nouvelle de l’algorithmique a pris forme ces dernières années. Alors qu’ils ont été longtemps de simples outils de conception pour la programmation, les algorithmes sont en passe d’acquérir, au sein des sciences et des technologies nouvelles, le rôle qu’ont traditionnellement tenu, dans les sciences physiques, les équations aux dérivées partielles. La biologie des systèmes, la modélisation du cerveau, les sciences sociales, l’économie et les sciences des réseaux sont autant de domaines où le processus algorithmique est au cœur de l’action. De fait, la portée de certains algorithmes s’étend bien au delà de leur cadre proprement informatique. On pense à l’impact créé en physique quantique par l’algorithme de factorisation de Shor ; à PageRank, le moteur de recherches de Google, dont le succès doit à une approche syntactique de questions sémantiques, ou encore à AdaBoost, l’algorithme qui a transformé l’apprentissage automatique. Ces développements, dont les retombées concrètes ne sont plus à démontrer, sont, tous les trois, issus de l’algorithmique.

L'algorithmique et les sciences

Richard Pollack

Jacob E. Goodman

This volume is a collection of refereed expository and research articles in discrete and computational geometry written by leaders in the field. Articles are based on invited talks presented at the AMS-IMS-SIAM Summer Research Conference, ``Discrete and Computational Geometry: Ten Years Later'', held in 1996 at Mt. Holyoke College (So. Hadley, MA). Topics addressed range from tilings, polyhedra, and arrangements to computational topology and visibility problems. Included are papers on the interaction between real algebraic geometry and discrete and computational geometry, as well as on linear programming and geometric discrepancy theory.

Proceedings of the 1996 AMS-IMS-SIAM Joint Summer Research Conference, Discrete and Computational Geometry--Ten Years Later, July 14-18, 1996, Mount Holyoke College

Bernard Chazelle

About

Books

Join the club