Computation, combinatorics and probability

We have been made aware of a convincing email scam that is focusing on our Programme and Workshop participants. Participants may receive an email from a firm called Expo Hotel Services (ehotelservices.org) to arrange accommodation for workshops and/or programmes. This might include a request to provide them with credit card information.

Please note, INI will never ask for your card details. We take all payments via the University of Cambridge Online store https://onlinesales.admin.cam.ac.uk/.

If you have been contacted by this company please contact us as soon as possible.

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

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