Schedule

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:

Plenary speakers will include:

Financial support for this workshop was provided in part by Microsoft Research.