skip to content

Randomised Algorithms

5th August 2002 to 16th August 2002

Organisers: Martin Dyer (Leeds), Mark Jerrum (Edinburgh), Peter Winkler (Bell Labs)

Supported by the European Commission, Research DG, Human Potential Programme, High-Level Scientific Conferences - HPCF-2001-00105

Conference Theme

As the analysis of algorithms has matured as a discipline, it has drawn from (and inspired) increasingly sophisticated mathematics. This is particularly true of the analysis of randomised algorithms. The conference aims to stimulate progress in this interdisciplinary area, by bringing together computer scientists with probability theorists and others working in relevant areas of mathematics, such as the theory of stochastic processes.


The programme is in two parts. The first part will be concerned with mathematical foundations, for example, random walks on graphs, concentration of measure, etc. The second part is concerned with design and analysis of algorithms which make random choices - including Monte Carlo and Markov chain Monte Carlo (MCMC) algorithms and deterministic algorithms when run on random instances. The main criterion for inclusion of an application is that the analysis should make significant and preferably novel use of tools from probability theory. The first Monday and Tuesday of the conference may be used for introductory and survey talks, designed to orient newcomers to the topics.

University of Cambridge Research Councils UK