skip to content
 

Timetable (CMPW01)

Randomised Algorithms

Monday 5th August 2002 to Friday 16th August 2002

Monday 5th August 2002
08:30 to 10:00 Registration
Session: Randomised Algorithms
INI 1
11:00 to 11:15 Coffee
Session: Randomised Algorithms
INI 1
11:15 to 11:30 Welcome by Director
Session: Randomised Algorithms
INI 1
11:30 to 12:30 S Janson ([Uppsala])
Estimates for large deviations of sums of dependent variables
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 C Smyth ([IAS, Princeton])
Reimer's inequality and a conjecture of Tardos
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 M Jerrum ([Edinburgh])
Mixing time and its relation to other Markov chain parameters
Session: Randomised Algorithms
INI 1
17:15 to 18:15 Welcome Wine Reception
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Tuesday 6th August 2002
10:00 to 11:00 R Kannan ([Yale])
Blocking Conductance --- an improved measure of convergence
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 C Greenhill ([Melbourne])
The differential equations method
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 A Barvinok ([Michigan])
The distribution of values in the quadratic assignment problem
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 C Cooper ([Goldsmiths])
The cover time of sparse random graphs $G_{n,p}$, $p=c \log n$, $c>1$, and related problems
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Wednesday 7th August 2002
10:00 to 11:00 A Holroyd ([Univ. of California at Los Angeles])
Two-dimensional bootstrap percolation
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 M Safra ([Tel Aviv])
Noise - insensitive Boolean - functions are juntas
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Thursday 8th August 2002
10:00 to 11:00 P Tetali ([Georgia Tech])
Approximating Min-sum set cover
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 E Vigoda ([Chicago])
Mixing in time and space for lattice spin system: a combinatorial view
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 A Sokal ([New York])
Chromatic polynomials, Potts models, and all that
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 M Cryan ([Leeds])
A polynominal-time algorithm to approximately count contingency tables when the number of rows is constant
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Friday 9th August 2002
10:00 to 11:00 D Randall ([Georgia Tech])
Random dyadic tilings of the unit square
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 M Mahoney ([Yale])
Markov chan Monte Carlo in statistical physics \& an application to the statistical mechanics of simple models of liquid water
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 G Brightwell (London School of Economics)
Connectedness of Glauber dynamics for H-coloring
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 P Winkler ([Bell Labs])
Mixing \& shuffling
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Monday 12th August 2002
10:00 to 11:00 T Gowers ([Cambridge])
Arithmetic progressions and Fourier analysis
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 A Sinclair ([UC Berkeley])
Clifford algebras and approximating the permanent
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 L Goldberg ([Warwick])
The compexity of sampling (and approximately counting graph homomorphism
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 M Dyer ([Leeds])
Approximate counting by dynamic programming
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Tuesday 13th August 2002
10:00 to 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
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 M Zito ([Liverpool])
(Distance constrained) edge packing in random regular graphs
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 A Rucinski ([AMU, Poznan])
Ramsey properties of random structures
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 C Banderier ([MPI])
Discrete smoothed complexity
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Wednesday 14th August 2002
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 J Hansen ([Heriot-Watt])
Hueristic algorithms for optimal directed spanning trees...
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
20:00 to 00:00 Conference Dinner at Magdalene College
Session: Randomised Algorithms
INI 1
Thursday 15th August 2002
10:00 to 11:00 M Karonski ([Adam Mickiwicz University, Poznan])
Existence of a perfect matching in a random (1 + 1/e)-out bipartite graph
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 A Frieze ([CMU Pittsburgh])
Perfect matchings in random graphs with prescribed minimal degree
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 M Luczak ([Cambridge])
Building uniform subtrees of a Cayley tree
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 G Sorkin ([IBM])
Phase transitions in random MAX 2-SAT and MAX CUT
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
Friday 16th August 2002
10:00 to 11:00 J Fill (Johns Hopkins University)
On the possibility, and impossiblity, of interruptible perfect sampling
Session: Randomised Algorithms
INI 1
11:00 to 11:30 Coffee
Session: Randomised Algorithms
INI 1
11:30 to 12:30 A Czumaj (New Jersey Institute of Technology)
Simple strategies for high-precision load balancing
Session: Randomised Algorithms
INI 1
12:30 to 13:30 Lunch at Wolfson Court
Session: Randomised Algorithms
INI 1
14:00 to 15:00 V Vazirani ([Georgia Tech])
A stochastic process on the hypercube with applications to peer-to-peer networks
Session: Randomised Algorithms
INI 1
15:00 to 15:30 Tea
Session: Randomised Algorithms
INI 1
16:00 to 17:00 M Karpinski ([Bonn])
Approximating dense instances of MIN-SAT
Session: Randomised Algorithms
INI 1
18:45 to 19:30 Dinner at Wolfson Court (Residents only)
Session: Randomised Algorithms
INI 1
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons