Breadcrumb
Randomness and complexity
03 July 2006 to
07 July 2006
Contact Person: Cathy Badley
Organisers: Dominic Welsh, Mark Jerrum
Description
Workshop held by the Heilbronn Instiute/University of Bristol
Main Speakers
- Magnus Bordewich (Durham): Optimising metrics in path coupling
- Graham Brightwell (LSE): Extremal subgraphs of random graphs
- Harry Buhrman (Amsterdam): Kolmogorov complexity & computational complexity
- Mary Cryan (Edinburgh): Approximately counting lattice points
- Irit Dinur (Hebrew University): The PCP Theorem by gap amplification
- Martin Dyer (Leeds): Randomly colouring bipartite graphs
- Alan Frieze (Carnegie Mellon): Line-of-sight networks
- Lance Fortnow (Chicago): Computational depth
- Leslie Ann Goldberg (Warwick): Inapproximability of the Tutte polynomial
- Oded Goldreich (Weizmann Institute): Pseudorandomness
- Colin McDiarmid (Oxford): The maximum degree of a random planar graph
- Russell Martin (Liverpool): Recent results about load balancing
- Steven Noble (Brunel): Evaluating graph polynomials in polynomial time
- Alistair Sinclair (Berkeley): Reconstruction problems on trees
- Luca Trevisan (Berkeley): Gowers uniformity
- V Vazirani (Georgia): New market models and algorithms