Isaac Newton Institute for Mathematical Sciences

A Newton Institute Workshop

Randomised Algorithms

5 Aug - 16 Aug 2002

Timetable:

List of participants

Monday 5 August

08.30-10.00 Registration

11.00-11.15 Coffee

11.15-11.30 Welcome by Director

11.30-12.30 S Janson (Uppsala)

Estimates for large deviations of sums of dependent variables

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 C Smyth (IAS, Princeton)

Reimer's inequality and a conjecture of Tardos

15.00-15.30 Tea

16.00-17.00 M Jerrum (Edinburgh)

Mixing time and its relation to other Markov chain parameters

17.15-18.15 Welcome Wine Reception

18.45-19.30 Dinner at Wolfson Court (Residents only)

Tuesday 6 August

10.00-11.00 R Kannan (Yale)

Blocking Conductance --- an improved measure of convergence

11.00-11.30 Coffee

11.30-12.30 C Greenhill (Melbourne)

The differential equations method

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 A Barvinok (Michigan)

The distribution of values in the quadratic assignment problem

15.00-15.30 Tea

16.00-17.00 C Cooper (Goldsmiths)

The cover time of sparse random graphs
$G_{n,p}$, $p=c \log n$, $c>1$, and related problems

18.45-19.30 Dinner at Wolfson Court (Residents only)

Wednesday 7 August

10.00-11.00 A Holroyd (Univ. of California at Los Angeles)

Two-dimensional bootstrap percolation

11.00-11.30 Coffee

11.30-12.30 M Safra (Tel Aviv)

Noise - insensitive Boolean - functions are juntas

12.30-13.30 Lunch at Wolfson Court

18.45-19.30 Dinner at Wolfson Court (Residents only)

Thursday 8 August

10.00-11.00 P Tetali (Georgia Tech)

Approximating Min-sum set cover

11.00-11.30 Coffee

11.30-12.30 E Vigoda (Chicago)

Mixing in time and space for lattice spin system: a combinatorial view

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 A Sokal (New York)

Chromatic polynomials, Potts models, and all that

15.00-15.30 Tea

16.00-17.00 M Cryan (Leeds)

A polynominal-time algorithm to approximately count contingency
tables when the number of rows is constant

18.45-19.30 Dinner at Wolfson Court (Residents only)

Friday 9 August

10.00-11.00 D Randall (Georgia Tech)

Random dyadic tilings of the unit square

11.00-11.30 Coffee

11.30-12.30 M Mahoney (Yale)

Markov chan Monte Carlo in statistical physics & an application
to the statistical mechanics of simple models of liquid water

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 G Brightwell (London School of Economics)

Connectedness of Glauber dynamics for H-coloring

15.00-15.30 Tea

16.00-17.00 P Winkler (Bell Labs)

Mixing & shuffling

18.45-19.30 Dinner at Wolfson Court (Residents only)

Monday 12 August

10.00-11.00 T Gowers (Cambridge)

Arithmetic progressions and Fourier analysis

11.00-11.30 Coffee

11.30-12.30 A Sinclair (UC Berkeley)

Clifford algebras and approximating the permanent

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 L Goldberg (Warwick)

The compexity of sampling (and approximately counting
graph homomorphism

15.00-15.30 Tea

16.00-17.00 M Dyer (Leeds)

Approximate counting by dynamic programming

18.45-19.30 Dinner at Wolfson Court (Residents only)

Tuesday 13 August

10.00-11.00 JH Kim (Microsoft Research, Redmond)

The Poisson cloning model for random graphs with applications to
k-core problems, random 2-SAT, and random digraphs

11.00-11.30 Coffee

11.30-12.30 M Zito (Liverpool)

(Distance constrained) edge packing in random regular graphs

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 A Rucinski (AMU, Poznan)

Ramsey properties of random structures

15.00-15.30 Tea

16.00-17.00 C Banderier (MPI)

Discrete smoothed complexity

18.45-19.30 Dinner at Wolfson Court (Residents only)

Wednesday 14 August

11.00-11.30 Coffee

11.30-12.30 J Hansen (Heriot-Watt)

Hueristic algorithms for optimal directed spanning trees...

12.30-13.30 Lunch at Wolfson Court

20.00- . Conference Dinner at Magdalene College

Thursday 15 August

10.00-11.00 M Karonski (Adam Mickiwicz University, Poznan)

Existence of a perfect matching in a random (1 + 1/e)-out bipartite
graph

11.00-11.30 Coffee

11.30-12.30 A Frieze (CMU Pittsburgh)

Perfect matchings in random graphs with prescribed minimal degree

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 M Luczak (Cambridge)

Building uniform subtrees of a Cayley tree

15.00-15.30 Tea

16.00-17.00 G Sorkin (IBM)

Phase transitions in random MAX 2-SAT and MAX CUT

18.45-19.30 Dinner at Wolfson Court (Residents only)

Friday 16 August

10.00-11.00 J Fill (Johns Hopkins University)

On the possibility, and impossiblity, of interruptible
perfect sampling

11.00-11.30 Coffee

11.30-12.30 A Czumaj (New Jersey Institute of Technology)

Simple strategies for high-precision load balancing

12.30-13.30 Lunch at Wolfson Court

14.00-15.00 V Vazirani (Georgia Tech)

A stochastic process on the hypercube with applications
to peer-to-peer networks

15.00-15.30 Tea

16.00-17.00 M Karpinski (Bonn)

Approximating dense instances of MIN-SAT

18.45-19.30 Dinner at Wolfson Court (Residents only)


Webmaster
Copyright © 1996 Isaac Newton Institute.
Updated at 11:35 on 15 August 2002