DIMACS/IAS Workshop on Randomized and Derandomized Algorithms for Discrete Structures

November 2 - 4, 1998
Institute for Advanced Study, Princeton, NJ

Organizers:
Bruce Reed, Universite Pierre et Marie Curie, reed@ecp6.jussieu.fr
Noga Alon, Tel Aviv University and IAS, noga@math.tau.ac.il
Alan Frieze, Carnegie Mellon University, frieze@random.math.cmu.edu
Presented under the auspices of the Special Year on Large Scale Discrete Optimization.

Co-sponsored by DIMACS and the Institute for Advanced Study

This workshop is devoted to two techniques which have wide application in theoretical discrete optimization: the semi-random method and Szemeredi's Regularity Lemma (by the semi-random method we mean the generation of combinatorial objects via repeated applications of the probabilistic method, e.g. the Rodl nibble or iterative applications of the Lovasz Local Lemma). The second of these techniques applies only to large graphs. Most applications of the first are to large structures. This explains the choice of these topics as the subject of a workshop held under the auspices of the Special Year on Large-Scale Discrete Optimization.

The Regularity Lemma states roughly that the vertices of any large enough graph can be split up into pieces so that the bipartite graph spanned by the edges between each pair of pieces behaves essentially like a random bipartite graph. Thus, it seems reasonable that the resultant structure is amenable to analysis via the semi-random method. The most ambitious goal of the workshop is to foster collaborative research projects which combine the Regularity Lemma and the semi-random method. However, the presentations given at the workshop will not be so narrowly focussed. There will be no contributed talks.

Limited funds are available to support participants.

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on September 1, 1998.