Randomised algorithms

Workshop theme

Supported by the European Commission, Research DG, Human Potential Programme, High-Level Scientific Conferences - HPCF-2001-00105

As the analysis of algorithms has matured as a discipline, it has drawn from (and inspired) increasingly sophisticated mathematics. This is particularly true of the analysis of randomised algorithms. The conference aims to stimulate progress in this interdisciplinary area, by bringing together computer scientists with probability theorists and others working in relevant areas of mathematics, such as the theory of stochastic processes.

Structure

The programme is in two parts. The first part will be concerned with mathematical foundations, for example, random walks on graphs, concentration of measure, etc. The second part is concerned with design and analysis of algorithms which make random choices - including Monte Carlo and Markov chain Monte Carlo (MCMC) algorithms and deterministic algorithms when run on random instances. The main criterion for inclusion of an application is that the analysis should make significant and preferably novel use of tools from probability theory. The first Monday and Tuesday of the conference may be used for introductory and survey talks, designed to orient newcomers to the topics.

The application is closed

Timetable

Monday 5th August 2002
08:30 to 10:00	Registration	Room 1
11:00 to 11:15	Coffee	Room 1
11:15 to 11:30	Welcome by Director	Room 1
11:30 to 12:30	Svante Janson Estimates for large deviations of sums of dependent variables	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Clifford Smyth Institute for Advanced Study, Princeton Reimer's inequality and a conjecture of Tardos	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	Mixing time and its relation to other Markov chain parameters	Room 1
17:15 to 18:15	Welcome Wine Reception	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Tuesday 6th August 2002
10:00 to 11:00	Blocking Conductance --- an improved measure of convergence	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	The differential equations method	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Alexander Barvinok University of Michigan The distribution of values in the quadratic assignment problem	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	The cover time of sparse random graphs $G_{n,p}$, $p=c \log n$, $c>1$, and related problems	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Wednesday 7th August 2002
10:00 to 11:00	Two-dimensional bootstrap percolation	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Noise - insensitive Boolean - functions are juntas	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Thursday 8th August 2002
10:00 to 11:00	Presad Tetali Georgia Institute of Technology Approximating Min-sum set cover	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Mixing in time and space for lattice spin system: a combinatorial view	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Alan Sokal New York University Chromatic polynomials, Potts models, and all that	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	A polynominal-time algorithm to approximately count contingency tables when the number of rows is constant	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Friday 9th August 2002
10:00 to 11:00	Dana Randall Georgia Institute of Technology Random dyadic tilings of the unit square	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Michael Mahoney Stanford University Markov chan Monte Carlo in statistical physics \& an application to the statistical mechanics of simple models of liquid water	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Connectedness of Glauber dynamics for H-coloring	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	Peter Winkler Mixing \& shuffling	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Monday 12th August 2002
10:00 to 11:00	Arithmetic progressions and Fourier analysis	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Alistair Sinclair Clifford algebras and approximating the permanent	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Leslie Goldberg University of Warwick The compexity of sampling (and approximately counting graph homomorphism	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	Approximate counting by dynamic programming	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Tuesday 13th August 2002
10:00 to 11:00	Jeong Han Kim Microsoft (UK) The Poisson cloning model for random graphs with applications to k-core problems, random 2-SAT, and random digraphs	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Michele Zito University of Liverpool (Distance constrained) edge packing in random regular graphs	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Andrzej Rucinski IFT-UAM/CSIC Ramsey properties of random structures	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	Discrete smoothed complexity	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Wednesday 14th August 2002
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Hueristic algorithms for optimal directed spanning trees...	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
20:00 to 00:00	Conference Dinner at Magdalene College	Room 1

Thursday 15th August 2002
10:00 to 11:00	Michal Karonski Adam Mickiewicz University Existence of a perfect matching in a random (1 + 1/e)-out bipartite graph	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Alan Frieze Carnegie Mellon University Perfect matchings in random graphs with prescribed minimal degree	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Thomasz Luczak Adam Mickiewicz University Building uniform subtrees of a Cayley tree	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	Gregory Sorkin IBM Research Phase transitions in random MAX 2-SAT and MAX CUT	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Friday 16th August 2002
10:00 to 11:00	Jim Fill Johns Hopkins University On the possibility, and impossiblity, of interruptible perfect sampling	Room 1
11:00 to 11:30	Coffee	Room 1
11:30 to 12:30	Simple strategies for high-precision load balancing	Room 1
12:30 to 13:30	Lunch at Wolfson Court	Room 1
14:00 to 15:00	Vijay Vazirani A stochastic process on the hypercube with applications to peer-to-peer networks	Room 1
15:00 to 15:30	Tea	Room 1
16:00 to 17:00	Marek Karpinski University of Bonn Approximating dense instances of MIN-SAT	Room 1
18:45 to 19:30	Dinner at Wolfson Court (Residents only)	Room 1

Speakers

Alexander Barvinok University of Michigan
Jim Fill Johns Hopkins University
Alan Frieze Carnegie Mellon University
Leslie Goldberg University of Warwick
Svante Janson
Michal Karonski Adam Mickiewicz University
Marek Karpinski University of Bonn
Jeong Han Kim Microsoft (UK)
Thomasz Luczak Adam Mickiewicz University
Michael Mahoney Stanford University
Dana Randall Georgia Institute of Technology
Andrzej Rucinski IFT-UAM/CSIC
Alistair Sinclair
Clifford Smyth Institute for Advanced Study, Princeton
Alan Sokal New York University
Gregory Sorkin IBM Research
Presad Tetali Georgia Institute of Technology
Vijay Vazirani
Peter Winkler
Michele Zito University of Liverpool

Show All

Workshop theme

Structure

The application is closed

Timetable

Speakers

Supported By

Register for updates