SPECIAL YEAR ON GRAPH THEORY AND COMBINATORIAL
OPTIMIZATION
Workshop on Probabilistic Graph Theory
February 14 - 19, 2000
Scientific and Organizing Committee:
J. Cheriyan, University of Waterloo
A. Frieze, Carnegie Mellon University
M. Molloy, University of Toronto
J. Spinrad, Vanderbilt University
L. Stewart, University of Alberta
Probabilistic trends have been amongst the most important developments
in graph theory. Since its introduction by Erdos and others in the 1940's,
the probabilistic method has emerged as a powerful tool, and has yielded
many of the strongest recent results in Ramsey theory, graph colouring,
and many other areas. Rabin and others introduced randomization to the
design of algorithms in the 1970's, and now for many important problems,
the most attractive algorithms currently known are randomized ones.
The average-case analysis of algorithms has become a popular alternative
to the traditional worst-case analysis, since it has the potential of
bridging the gap between the pessimistic worst-case complexity of an
algorithm and the empirical performance of the algorithm. The study
of random graphs is crucial to each of these areas, and is also a fascinating
field on its own.
This workshop will serve to gather together researchers in
the various aspects of probabilistic graph theory to share recent work and
ideas, as well as to provide an opportunity for newcomers to the field to
learn. There will be a limited number of talks which will include both introductory
lectures aimed at the non-expert, and higher-level lectures in which participants
will present recent research.
Some of the topics will include:
1) The Probabilistic Method
2) Random Graphs
3) Randomized Algorithms
4) Probabilistic Analysis of Algorithms
Plenary speakers will include:
| Noga Alon Tel Aviv University |
Bruce Reed CNRS, Paris |
| Jennifer Chayes Microsoft Research |
Prabhakar Raghaven Almaden Research Centre, IBM |
| Luc Devroye McGill University |
Joel Spencer Courant Institute |
| Michael Steele University of Pennsylvania |
Financial support for this workshop was provided in part by Microsoft Research.
