December  4, 2022


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.