Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

Newton Institute Logo


in association with the Newton Institute programme entitled Computation, Combinatorics and Probability
(29 July to 20 December 2002)

16 - 20 DECEMBER 2002

Programme Abstracts Participants

Martin Dyer (Leeds), Leslie Goldberg (Warwick), Mark Jerrum (Edinburgh), Frank Kelly (Cambridge) and Peter Winkler (Bell Labs)

Theme of Conference:
The Internet raises all sorts of completely new algorithmic questions, and it is these that form the focus for this workshop. An important aspect of communication on the Internet (and in other modern networks) is absence of centralised control: users communicate with each other by sending messages over the net, and use local protocols to control transmissions and to handle collisions.

One would like to study protocols, for example TCP/IP, with the aim of providing a rigorous analysis of the performance of the network. This study combines traditional probabilistic analysis (characterising the long-term behaviour of Markov chains and other stochastic processes, which are used to model protocols) with economic analysis (issues of fairness/utility) and with more traditional network algorithmics (routing methods).

Evaluating the quality of the long-term equilibrium is related to game-theory. One would like to know, for example, how close the Nash equilibrium (which arises from local control) is to the overall optimum. However, the new twist is that issues of computational tractability must be taken into account.

A further category of problems, more combinatorial in nature, arises in the modelling of the web graph and its evolution. For this purpose, standard random-graph models are unsuitable. New models are required which are consistent with empirical observations, for example that the degree-sequence of the web graph apparently obeys a power law.

(List is partial and provisional)
Richard Gibbens (Cambridge), Elias Koutsoupias (UC, Los Angeles), Christos Papadimitriou (UC, Berkeley), Prabhakar Raghavan (Verity), Adi Rosen (Technion, Haifa)), Tim Roughgarden (Cornell), Bernhard von Stengel (London School of Economics), Eli Upfal (Brown, Providence, RI), Berthold Voecking (MPI, Saarbruecken)

Location and Cost:
The conference will take place at the Newton Institute and accommodation for participants will be provided in single study bedrooms with shared bathroom at Wolfson Court . The workshop package, costing £350, includes accommodation, breakfast and dinner from dinner on Sunday 15 December until breakfast on Saturday 21 December 2002, and lunch and refreshments during the days that lectures take place.

Further information
Please e-mail your enquiries to Tracey Andrew

Travel and Local Information

How to reach the Newton Institute | Local Information |

Computation, Combinatorics and Probability programme | Newton Institute Home Page |