RANDOMISED AND APPROXIMATE COMPUTATION
Workshop
to be held in Mathematical Institute,
from
: Wednesday, 10 December
to
:
Final Programme
WEDNESDAY
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.
THURSDAY
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
or
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
FRIDAY
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