Computation, combinatorics and probability

Programme theme

As Computer Science has matured as a discipline, its relationships with mathematics have become both more wide ranging and more profound. The programme will explore two particularly fruitful interfaces between computer science and mathematics, namely those with combinatorics and probability theory. Although no interdisciplinary work within the broad area delineated by the title will be excluded, the following themes will receive special emphasis.

Randomised algorithms.
The design and analysis of algorithms that make random choices; also deterministic algorithms when run on random instances.The theoretical basis here includes the study of parameters connected with random walks on graphs and the relationships between them.
"Phase transitions" in statistical physics and computer science.
The rigorous treatment not only of infinite random systems,but also of (infinite sequences of) finite systems that exhibit phenomena akin to phase transitions. Particular attention willbe paid to the link between phase transitions and computational (in)tractability.
Random graphs and structures.
The analysis of finite random structures,of which the Erdos-Renyi random graph model is the primal example.Algorithmic aspects will receive special attention.
Probabilistic analysis of distributed systems.
The study of the behaviour of distributed systems in the absence of global control. Specific topics include contention resolution protocols and Nash equilibria of agents in networks (the Internet).The theoretical basis here includes Lyapunov functions and game theory.

Click here to download the programme's final scientific report

Preprints

Title	Year	Programme
Large deviations for sums of partly dependent random variables Authors: Svante Janson Download PDF	2002	CMP	21 October 2016
A polynomial bound on the diameter of the transportation polytope Authors: Leen Stougie Download PDF	2002	CMP	21 October 2016
Upper tails for subgraph counts in random graphs Authors: K Oleszkiewicz, Andrzej Rucinski, Svante Janson Download PDF	2002	CMP	21 October 2016
Random hypergraph processes with degree restrictions Authors: C Greenhill, NC Wormald, Andrzej Rucinski Download PDF	2002	CMP	21 October 2016
Polynomial time approximation schemes for metric MIN-BISECTION Authors: W Fernandez De La Vega, Marek Karpinski, C Kenyon Download PDF	2002	CMP	21 October 2016
Random Sampling of 3-colourings in $\mathbb{Z}^2$ Authors: Paul Wilfred Goldberg, Russell Martin, Michael Paterson Download PDF	2002	CMP	21 October 2016
A quadratic bound on the diameter of the transportation polytope Authors: J Van Den Heuvel, Leen Stougie Download PDF	2002	CMP	21 October 2016
The vertex degree distribution of random intersection graphs Authors: D Stark Download PDF	2002	CMP	21 October 2016
Approximation schemes for clustering problems in finite metrics and high dimensional spaces Authors: Marek Karpinski, C Kenyon, ET Al, W Fernandez De La Vega Download PDF	2002	CMP	21 October 2016
On approximability of minimum bisection problem Authors: Marek Karpinski Download PDF	2002	CMP	21 October 2016
9/8-Approximation Algorithm for Random MAX-3SAT Authors: Marek Karpinski, W Fernandez De La Vega Download PDF	2002	CMP	21 October 2016
The geometry of logoncave functions and an ${\it 0(n^3)}$ sampling algorithm Authors:* S Vempala, L Lovasv Download PDF	2002	CMP	21 October 2016
Hit-and-run is fast and fun Authors: S Vempala, L Lovasv Download PDF	2002	CMP	21 October 2016
Invasion percolation and the incipient infinite cluster in 3D Authors: Antal Jarai Download PDF	2002	CMP	21 October 2016
On the structure of the core of sparse random graphs Authors: Nikolaos Fountoulakis Download PDF	2002	CMP	21 October 2016
A second threshold for the hard-core model on a Bethe lattice Authors: GR Brightwell, Peter Winkler Download PDF	2002	CMP	21 October 2016
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains Authors: Jung-Bae Son, Prasad Tetali, ET Al, M Jerrum Download PDF	2002	CMP	21 October 2016
How many graphs are unions of ${\it k}$-cliques? Authors: GR Brightwell, ET Al, Bela Bollobas Download PDF	2002	CMP	21 October 2016
The random-cluster model Authors: G Grimmett Download PDF	2002	CMP	21 October 2016
On smallest triangles Authors: G Grimmett, Svante Janson Download PDF	2002	CMP	21 October 2016
Negative correlation of edge events on uniform spanning forests Authors: G Grimmett, Peter Winkler Download PDF	2002	CMP	21 October 2016

Workshops

CMPW01

Randomised algorithms

5 August 2002 to 16 August 2002

CMPW02

Combinatorial and computational aspects of statistical physics/random graphs and structures

27 August 2002 to 6 September 2002

CMPW03

Topics in computer communication and networks

15 December 2002 to 21 December 2002

Seminars

Wednesday 25th September 2002
14:00 to 15:00	Thomasz Luczak Adam Mickiewicz University The phase transiton in random graphs: a microscopic view of the random-cluster model	Room 2

Thursday 26th September 2002
11:00 to 12:00	Peter Winkler On playing golf with two balls	Room 2

Wednesday 2nd October 2002
16:00 to 17:00	Antal Jarai University of British Columbia Incipient infinite percolation clusters in two and high dimensions	Room 2

Tuesday 8th October 2002
14:00 to 15:00	Miklos Simonovits Aalborg Universitet On a hypergraph extremal problem	Room 1

Tuesday 15th October 2002
16:00 to 17:00	Self-destructive percolation	Room 1

Wednesday 23rd October 2002
16:00 to 17:00	Lukacs Aalborg Universitet Generating random group elements	Room 1

Tuesday 29th October 2002
16:00 to 17:00	Leen Stougie On-line optimisation	Room 1

Tuesday 12th November 2002
16:00 to 17:00	Dana Randall Georgia Institute of Technology Simulated tempering: fast or slow?	Room 1

Tuesday 19th November 2002
16:00 to 17:00	Non-Markovian coupling	Room 1

Tuesday 26th November 2002
16:00 to 17:00	Markov chains for contingency tables with few rows	Room 1

Tuesday 3rd December 2002
16:00 to 17:00	Stochastic process methods in the analysis of random hypergraphs	Room 1

Tuesday 10th December 2002
16:00 to 17:00	Cyclic colourings and distant 2-colourings of planar graphs	Room 2

Computation, combinatorics and probability

Organisers

Martin Dyer University of Leeds

Speakers

Antal Jarai University of British Columbia
Thomasz Luczak Adam Mickiewicz University
Lukacs Aalborg Universitet
Dana Randall Georgia Institute of Technology
Miklos Simonovits Aalborg Universitet
Leen Stougie
Peter Winkler

Computation, combinatorics and probability

Programme theme

Preprints

Large deviations for sums of partly dependent random variables

A polynomial bound on the diameter of the transportation polytope

Upper tails for subgraph counts in random graphs

Random hypergraph processes with degree restrictions

Polynomial time approximation schemes for metric MIN-BISECTION

Random Sampling of 3-colourings in $\mathbb{Z}^2$

A quadratic bound on the diameter of the transportation polytope

The vertex degree distribution of random intersection graphs

Approximation schemes for clustering problems in finite metrics and high dimensional spaces

On approximability of minimum bisection problem

9/8-Approximation Algorithm for Random MAX-3SAT

The geometry of logoncave functions and an ${\it 0*(n^3)}$ sampling algorithm

Hit-and-run is fast and fun

Invasion percolation and the incipient infinite cluster in 3D

On the structure of the core of sparse random graphs

A second threshold for the hard-core model on a Bethe lattice

Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains

How many graphs are unions of ${\it k}$-cliques?

The random-cluster model

On smallest triangles

Negative correlation of edge events on uniform spanning forests