skip to content

Computation, Combinatorics and Probability

Participation in INI programmes is by invitation only. Anyone wishing to apply to participate in the associated workshop(s) should use the relevant workshop application form.

29th July 2002 to 20th December 2002
Mark Jerrum University of Edinburgh
Martin Dyer University of Leeds
Peter Winkler [Bell Labs], [Bell Laboratories]


Programme Theme

As Computer Science has matured as a discipline, its relationships with mathematics have become both more wide ranging and more profound. The programme will explore two particularly fruitful interfaces between computer science and mathematics, namely those with combinatorics and probability theory. Although no interdisciplinary work within the broad area delineated by the title will be excluded, the following themes will receive special emphasis.

  • Randomised algorithms.
    The design and analysis of algorithms that make random choices; also deterministic algorithms when run on random instances.The theoretical basis here includes the study of parameters connected with random walks on graphs and the relationships between them.
  • "Phase transitions" in statistical physics and computer science.
    The rigorous treatment not only of infinite random systems,but also of (infinite sequences of) finite systems that exhibit phenomena akin to phase transitions. Particular attention willbe paid to the link between phase transitions and computational (in)tractability.
  • Random graphs and structures.
    The analysis of finite random structures,of which the Erdos-Renyi random graph model is the primal example.Algorithmic aspects will receive special attention.
  • Probabilistic analysis of distributed systems.
    The study of the behaviour of distributed systems in the absence of global control. Specific topics include contention resolution protocols and Nash equilibria of agents in networks (the Internet).The theoretical basis here includes Lyapunov functions and game theory.
Final Scientific Report: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons