Workshop to be held in Mathematical Institute, Oxford


from :      Wednesday, 10 December


to :          Friday, 12 December 2003








Final Programme





9.30     Marek Karpinski

Approximability of hypergraph minimum bisection.


10.15   Andrzej Lingas

Improved approximation algorithms for optimisation problems in graphs with superlogarithmic treewidth (joint work with A. Czumaj and J. Nilsson)


10.50   COFFEE


11.20   Leslie Goldberg

Sampling colourings on the triangular lattice.


12.05   Peter Cameron

Random Latin squares.



1.00     LUNCH



2.15     Robert Leese

Radio spectrum assignment meets economics.


2.50     Simon Blackburn

Codes used in copyright protection: how good are probabilistic methods?


3.35     Leszek Gasieniec

The wakeup problem in radio networks.


4.10     TEA


4.40     Michele Zito

Dominating sets in web-graphs.


5.15     Mark Jerrum

Approximating one Markov chain by another.



9.30     Stefanie Gerke

Szemeredi’s regularity in the sparse setting (Part I).


10.15   Magnus Bordewich

Approximate counting and quantum computation


10.50   COFFEE


11.20   Moni Naor

Know thy neighbour’s neighbour


Non-greedy routing algorithms are optimal.


12.05   Angelika Steger

Szemeredi’s regularity in the sparse setting (Part II).



1.00       LUNCH



2.00      Evangelos Kranakis

            Node Discovery in Ad-hoc Networks


2.35     Colin Cooper

Web graph models.


3.20     Andrew Goodall

Score vectors and vertex colourings.


3.55     TEA


4.25     Frederic Havet

Design of fault tolerant on-board networks with priorities.


5.00     Steven Noble

The domination number of greedy algorithms for the frequency assignment problem.


5.35     Andrew Thomason

Edge weights and vertex colourings.

6.15     RECEPTION




9.30     Martin Dyer

Colouring graphs randomly.


10.15   Stephane Boucheron

Moment inequalities for functions of many independent variables


10.50   COFFEE


11.20   Omer Gimenez

On the hardness of computing the number of bases of a bicircular matroid.


11.55   Hans-Jürgen Prömel

Random planar graphs.


12.30        Colin McDiarmid

Random load-balancing in continuous time

(based on joint work with Malwina Luczak).



1.10     LUNCH