RAND-APX Workshop, ICMS Edinburgh: Provisional Programme
Sunday 17th September
- 10:00-11:00. Contributed talks
- Marek Karpinski (Bonn):
``Improved approximation of MAX-CUT on graphs of bounded degree''
- Andrzej Lingas (Lund):
``A PTAS for Max-bisection on planar graphs''
- 11:00-11:30. Coffee
- 11:30-12:30. Contributed talks
- Joachim Buhmann (Bonn):
``Empirical risk approximation for data clustering''
- Colin Cooper (Goldsmiths College, London):
``Hamilton cycles in random r-regular graphs
for large r''
- 12:30-14:00. Lunch (hot buffet)
- 14:00-15:00. Invited talk
Andrew Stuart (Warwick): ``Algorithms for collision
detection amongst spheres''
- 15:00-15:30. Coffee
- 15:30-17:00. Contributed talks
- Petra Berenbrink (Warwick),
``Balanced allocations: The heavily loaded case or
`balls-into-bins games' ''
- Malwina Luczak (Oxford):
``Discrete-time balanced allocations in fully-connected networks''
- TBA
Monday 18th September
- 09:30-10:30. Invited talk
Roman Kotecky (Charles University, Prague):
``Mathematics of phase transitions''
- 10:30-11:00. Coffee
- 11:00-12:30. Contributed talks
- Joachim Gudmundsson (Lund):
``Improved algorithms for constructing sparse geometric spanners''
- Miklos Santha (Paris Sud), ``Semantical counting circuits''
- TBA
- 12:30-14:00. Lunch (cold buffet)
- 14:00-15:00. Invited talk
Marek Biskup (Microsoft Research):
``Statistical mechanics with complex weights: rigorous theory of
partition function zeros''
- 15:00-15:30. Coffee
- 15:30-17:00. Contributed talks
- Mark Jerrum (Edinburgh): Approximating the permanent (part I)
- Eric Vigoda (Edinburgh): Approximating the permanent (part II)
- TBA
Tuesday 19th September
- 09:30-10:30. Invited talk
Prasad Tetali (Georgia Tech):
``Poincaré, Cheeger and log-Sobolev''
- 10:30-11:00. Coffee
- 11:00-12:30. Contributed talks
- Martin Dyer (Leeds): ``Markov chains for random H-colourings''
- Leslie Goldberg (Warwick):
``On the relative complexity of approximate counting problems''
- TBA
End of the meeting
Mark Jerrum
Last modified: Thu Sep 14 18:13:57 BST 2000