The 12th International Conference on
RANDOM STRUCTURES AND ALGORITHMS
Poznan, 1-5 August 2005

Outline

Monday Tuesday Wednesday Thursday Friday
Opening

Frieze

Lovasz

Haxell

Upfal

Hastad
Coffee break
Thomason Tardos Cooper
Srivastav
Friedgut
Pikhurko
Feige
Vigoda
PHOTO Katona Czumaj Goldberg Jain
Lunch
Gerke
Polcyn
Nagle
Stojakovic
Banderier
Neininger
Ruzsinko
Bielak
Penman
Hansen
Kamenov
Erlihson
Janson Luczak
Wojciechowski
Seierstad
Hwang
Panholzer
Fuchs
Condon
Doerr
Delarue
Kral
Cichon
Vondrak
Coffee break
Sgall
Werth
Bachmat
Marciniszyn
Fernholz
Panagiotou
Balogh
Kaufman
Kang
Schlatter
Riordan Grytczuk
Lubetzky
Morris
McColm
Stark
Staples
Szabo
Huhn
Dombry
Szymanski
Kuba
Rudas
Random Run
EXCURSION Coja-Oghlan Cryan Johansson

Birthday Party

Farewell Party

Detailed schedule

Although the schedule is now complete, it is still subject to last minute changes.

Sunday, 31 July 2005

18:00-21:00 Dinner at Trawinski

Monday, 1 August 2005

9:15 Opening Address
9:30-10:30 Alan Frieze

Hamilton Cycles in 3-out.
Abstract: We show that G(3-out) is Hamiltonian whp.

10:30 Coffee break
11:00-12:00 Andrew Thomason

Random graphs, minors and the Erdős-Pósa Theorem

12:00 CONFERENCE PHOTO
13:00-14:00 Lunch
Conference Room 1 Conference Room 2
14:30-14:55 Stefanie Gerke
Algorithmic aspects of the regularity lemma for sparse graphs
Milos Stojakovic
Random Hamiltonian cycle game (and other games)
15:00-15:25 Joanna Polcyn
Large holes and short paths in quasi-random graphs
Cyril Banderier
On the Probabilty that God Wins at a Nim-Type Game
15:30-15:55 Brendan Nagle
Small subsystems of uniformly distributed 3-graphs
Ralph Neininger
Probabilistic analysis for randomized game tree evaluation
16:00 Coffee break
16:30-16:55 Jiri Sgall
Randomized algorithms in online scheduling
Martin Marciniszyn
Two-Stage Colorings Avoiding Monochromatic Triangles
17:00-17:25 Sören Werth
Probabilistic Analysis of a Multiple Depot Routing Problem
Daniel Fernholz
The Diameter of Sparse Random Graphs
17:30-17:55 Eitan Bachmat
Average case analysis of disk I/O scheduling and space-time geometry
Konstantinos Panagiotou
Unique Colorability of Random Graphs
19:00 BIRTHDAY PARTY

Tuesday, 2 August 2005

9:30-10:30 László Lovász

Random graphs and limits of graph sequences

10:30 Coffee break
11:00-12:00 Éva Tardos

Price of Anarchy or Stability in some Games on Networks

12:15-12:40 Gyula O.H. Katona
Most probably intersecting random families of subsets
13:00-14:00 Lunch
Conference Room 1 Conference Room 2
14:30-14:55 Miklos Ruzsinko
Three color Ramsey numbers for paths
Jennie Hansen
Hunting the Poisson-Dirichlet distribution
15:00-15:25 Halina Bielak
On size Ramsey numbers for some regular graphs
Emil Kamenov
The limiting distribution of the trace of a random plane partition
15:30-15:55 David Penman
Extremal Ramsey Graphs
Michael Erlihson
Limit shapes of expansive assemblies
16:00 Coffee break
16:30-16:55 Jozsef Balogh
Near-perfect pseudoharmonious matchings and paths in randomly labeled planar point sets
Mihyun Kang
Random cubic planar graphs
17:00-17:25 Tali Kaufman
Testing Triangle-Freeness in General Graphs
Dirk Schlatter
The random planar graph process
18:00 RANDOM RUN
19:00 Dinner

Wednesday, 3 August 2005

9:30-10:30 Penny Haxell

An algorithmic version of the hypergraph regularity method

10:30 Coffee break
11:00-11:25 Colin Cooper
The cover time of the giant component of G(n,p) and related problems
11:30-11:55 Anand Srivastav
Simultaneous Randomized Matching and Covering in Hypergraphs
12:00-12:25 Artur Czumaj
Clustering in metric spaces via sampling
13:00-14:00 Lunch
14:30 Bus to UAM Campus
15:00-16:00 Svante Janson

The phase transition in inhomogeneous random graphs

16:00 Coffee break
16:30-16:55 Olivier Riordan
The stability of the giant component
17:00-22:00 EXCURSION/BONFIRE

Thursday, 4 August 2005

9:30-10:30 Eli Upfal

Dynamic Stochastic Optimization

10:30 Coffee break
11:00-11:25 Ehud Friedgut
An analytic approach to Erdos-Ko-Rado type theorems
11:30-11:55 Oleg Pikhurko
Fragmentability of random d-regular graphs
12:00-12:25 Leslie Goldberg
Rapid Mixing for Systematic Scan Markov chains
13:00-14:00 Lunch
Conference Room 1 Conference Room 2
14:30-14:55 Malwina Luczak
A simple solution to the k-core problem
Hsien-Kuei Hwang
The width of random trees of logarithmic height
15:00-15:25 Jerzy Wojciechowski
Edge-Bandwidth of Grids and Tori
Alois Panholzer
On path covering numbers of random trees
15:30-15:55 Taral Seierstad
The phase transition in the minimum degree random graph process
Michael Fuchs
Phase changes in random point quadtrees
16:00 Coffee break
16:30-16:55 Jarek Grytczuk
Words, graphs, and drums
Gregory McColm
What's This about Weak Thresholds?
17:00-17:25 Eyal Lubetzky
The Shannon capacity of a graph and the independence numbers of its powers
Dudley Stark
Random Preorders
Break
17:45-18:10 Robert Morris
Hereditary properties of ordered hypergraphs
George Stacey Staples
Clifford Algebras and Random Graphs
18:15-18:40 Amin Coja-Oghlan
Counting connected hypergraphs via probabilistic methods
Mary Cryan
Approximately Counting Integral Flows
19:00 Dinner

Friday, 5 August 2005

9:30-10:30 Johan Hastad

PCPs and applications

10:30 Coffee break
11:00-11:25 Uriel Feige
Randomized algorithms for finding balanced separators

11:30-11:55 Eric Vigoda
Faster MCMCs for the Permanent and binary contingency tables
12:00-12:25 Kamal Jain
Building Scalable and Robust Peer-to-Peer Overlay Networks for Broadcasting using Network Coding
13:00-14:00 Lunch
Conference Room 1 Conference Room 2
14:30-14:55 Anne Condon
Arthur and Merlin take a walk
Daniel Kral
Three optimal algorithms for balls of three colors
15:00-15:25 Benjamin Doerr
The Propp Machine: Simulating Random Walks
Jacek Cichon
Random subsets of interval and Chord protocol
15:30-15:55 Francois Delarue
Distributed Algorithms in an Ergodic Markovian Environment
Jan Vondrak
The Minimum Spanning Tree and other problems for random subgraphs
16:00 Coffee break
16:30-16:55 Tibor Szabo
The randomized simplex algorithm is slow in abstract cubes
Jerzy Szymanski
On a scale-free tree
17:00-17:25 Petra Huhn
Probabilistic Analysis of Interior Point Methods for Linear Programming -- New Results for Gaussian Distribution
Markus Kuba
Isolating nodes in recursive trees
17:30-17:55 Clement Dombry
Data structures with dynamical random transitions
Anna Rudas
Random Trees and General Branching Processes
Break
18:15-18:40 Anders Johansson
Triangle factors of random graphs
19:00 Farewell Party