Randomness and complexity

26 Feb 2016, by chrystalcherniwchan in Events

Organisers: Dominic Welsh, Mark Jerrum

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