The 15th International Conference on
<br>RANDOM STRUCTURES AND ALGORITHMS, Atlanta, May 24-28, 2011

See also Outline

Lecture rooms in White Hall:
Invited talks - lecture room 208
session A - lecture room 206,
session B - lecture room 207.

Tuesday (24.05)

8:00-9:00 breakfast
9:00-9:05 Opening Ceremony
9:05-10:00 Béla Bollobás
The distribution of the number of vertices in the giant component (abstract)
10:00-10:30 coffee break
  A B
10:30-10:55 Dan Hefetz
Embedding spanning trees in random graphs near the connectivity threshold (abstract)
Fabio Martinelli
Sampling random surfaces: sharp mixing time bounds (abstract)
11:00-11:25 Daniel Johannsen
Tree Universality in Random Graphs(abstract)
Catherine Greenhill
Sampling regular directed graphs in polynomial time (abstract)
11:30-11:55Domingos Dellamonica
Universality of Random Graphs (abstract)
Cyril Roberto
Low temperature dynamics for the east model
12:00-1:30 lunch
1:30-2:25 Jeff Kahn
Upper tails for cliques
  A B
2:30-2:55 Lutz Warnke
Achlioptas process phase transitions are continuous (abstract)
Jane Butterfield
On the Chromatic Thresholds of Hypergraphs (abstract)
3:00-3:25 Tamas Makai
Triangle-free random graph process
Dmitry Shabanov
On colorings uniform hypergraphs with bounded edge degree (abstract)
3:25-3:50 coffee break
  A B
3:50-4:15 Hao Huang
Nonnegative $k$-sums, fractional covers and probability of small deviations (abstract)
Anant Godbole
Random Additive Bases
4:20-4:45 Hoi Nguyen
Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
Veronika Kraus
The degree profile in random Polya trees (abstract)
4:50-5:15 Wojciech Samotij
Sum-free sets in Abelian groups
Alan Frieze
Average-case performance of heuristics for three-dimensional random assignment problems (abstract)
5:15-5:25 break
5:25-5:50 Ke Wang
Eigenvalues and eigenvectors of sparse random graphs
Choongbum Lee
Large and judicious bisections of graphs (abstract)
5:55-6:20Po-Shen Loh
Rainbow Hamilton cycles in random graphs (abstract)
Charalampos Tsourakakis
High Degree Vertices, Eigenvalues and Diameter of Random Apollonian Networks (abstract)
6:30 Welcoming Reception

Wednesday (25.05)

8:00-9:00 breakfast
9:05-10:00 Subhash Khot
On the Unique Games Conjecture (abstract)
10:00-10:30 coffee break
  A B
10:30-10:55 Sonny Ben-Shimon
On the resilience of Hamiltonicity and optimal packing of Hamilton cycles in random graphs (abstract)
Ravi Montenegro
Conductance and canonical paths for directed non-lazy Markov Chains (abstract)
11:00-11:25 Pu Gao
Distributions of certain types of spanning subgraphs in G(n,p)
Andrew Beveridge
Exact Mixing Measures on Trees (abstract)
11:30-11:55 Simi Haber
Behavior of languages stronger than first order in G(n,p)
Thomas Hayes
Lifting Markov Chains for Faster Mixing
12:00-1:30 lunch
1:30-2:25 Jacob Fox
Graph regularity and removal lemmas (abstract)
  A B
2:30-2:55 Huseyin Acan
On a Giant Component in the Intersection Graph of a Random Chord Diagram (abstract)
Ido Ben-Eliezer
Local Rainbow Colorings (abstract)
3:00-3:25 Dieter Mitsche
Tree-like parameters in random geometric graphs
Sangjune Lee
The maximum size of a Sidon set contained in a sparse random set of integers (abstract)
3:25-3:50 coffee break
  A B
3:50-4:15 Jan Volec
Maximum cut in cubic graphs of large girth and in random cubic graphs
Louis DeBiasio
Posa's Conjecture (abstract)
4:20-4:45 Stephen Young
Diameter of Random Cubic Sum Graphs
Andreas Wuerfl
The Blow-up Lemma and growing degrees
4:45-4:55 break
  A B
4:55-5:20 Nikolaos Fountoulakis
Multiple orientability thresholds for random hypergraphs and applications (abstract)
Karthekeyan Chandrasekaran
Algorithms for Implicit Hitting Set Problems
5:25-5:50 Andrzej Dudek
On Hamilton Cycles in Random Hypergraphs (abstract)
6:30 -- ?? shuttles to Decatur

Thursday (26.05)

8:00-9:00 breakfast
9:05-10:00 Jennifer Chayes
Strategic Network Models: From Building to Bargaining (abstract)
10:00-10:30 Conference Photo
coffee break
  A B
10:30-10:55 Wesley Pegden
A best possible Local Lemma (abstract)
Mary Cryan
The number of Euler tours of random d-in/d-out graphs (abstract)
11:00-11:25 Christopher Ross
Longest Cycle Length in Random Difference Graphs (abstract)
Andrzej Grzesik
Maximum number of pentagons in triangle-free graphs (abstract)
11:30-11:55 Manuel Lladser
Doeblin's ergodicity coefficient: lower-complexity approximation of occupancy distributions (abstract)
Krzysztof Choromański
Upper bounds on Erdos-Hajnal coefficients of tournaments (abstract)
12:00-1:30 lunch
1:30-2:25 David Gamarnik
Statistical physics of random structures and algorithms
  A B
2:30-2:55 Jennie Hansen
Predecessors and successors in random mappings with exchangeable in-degrees (abstract)
Henning Thomas
Explosive Percolation in Erdös-Rényi-Like Random Graph Processes (abstract)
3:00-3:25 Maksim Zhukovskii
The law of large numbers for the frog model (abstract)
John Wierman
On equality of directional critical exponents in inhomogeneous percolation models
3:25-3:50 coffee break
  A B
3:50-4:15 Linyuan Lu
Generalized Laplacian Eigenvalues of Random Hypergraphs (abstract)
Christian Borgs
Left and Right Convergence for Sequences of Graphs with Bounded Degrees (abstract)
4:20-4:45 Joshua Cooper
Spectra of Hypergraphs (abstract)
Carlos Hoppen
Limits of sequences of combinatorial structures (abstract)
5:15 Random Run on Emory track
6:30 -- ?? shuttles to Decatur

Friday (27.05)

8:00-9:00 breakfast
9:05-10:00 Nick Wormald
Cops and Robber on random graphs
10:00-10:30 coffee break
  A B
10:30-10:55 David Galvin
The typical appearance of a colouring of a regular bipartite graph (abstract)
Miloš Stojaković
A threshold for the Maker-Breaker clique game (abstract)
11:00-11:25 Jakub Kozik
Nonrepetitive list colorings of trees. (abstract)
Torsten Mütze
Probabilistic one-player Ramsey games via deterministic two-player games (abstract)
11:30-11:55 Steve Butler
Finding patterns minimizing monochromatic constellations
Luca Gugelmann
A Randomized Version of Ramsey\'s Theorem
12:00-2:00 Random Run, lunch
2:00-2:55 Joel Spencer
Two Needles from Exponential Haystacks (abstract)
  A B
3:00-3:25 Anthony Bonato
Almost all cop-win graphs contain a universal vertex (abstract)
Johan Jonasson
On negative dependence
3:30-3:55 Paweł Prałat
Graphs with average degree smaller than 30/11 are burning slowly (abstract)
Varsha Dani
Independent sets in random graphs from the weighted second moment method
3:55-4:05 coffee break
  A B
4:05-4:30 Pawel Hitczenko
Some properties of random staircase tabelaux (abstract)
Colin Cooper
Component structure of the vacant set induced by a random walk on a random graph (abstract)
4:35-5:00 Ljuben Mutafchiev
The size of the largest part of random weighted partitions of large integers (abstract)
Jerzy Szymański
Connectivity of scale-free networks
  A B
5:05-5:30 He Sun
Approximate Counting of Cycles in Streams
Nicholas Georgiou
The simple harmonic urn (abstract)
5:35-6:00 Martin Fürer
Variations of Rasmussen's permanent approximation (abstract)
Tobias Mueller
The power of choices in random geometric graphs
6:30 Conference Banquet (6:30 drinks, 7:30 dinner) in Emory University Conference Center

Saturday (28.05)

8:00-9:00 breakfast
9:05-10:00 Eric Vigoda
Improved bound on the phase transition for independent sets in the square lattice (abstract)
10:00-10:30 coffee break
  A B
10:30-10:55 Mary Radcliffe
The Spectra of Random Graphs with General Distributions
Bernhard Gittenberger
On the Complexity of Boolean Functions Represented by Trees in Implicational Logic (abstract)
11:00-11:25 Andrei Raigorodskii
On various statistics of a random web-graph in the Bollobas--Riordan model (abstract)
Amit Weinstein
Local Correction of Boolean Functions
11:30-11:55 Jinwoo Shin
Efficiency and Signaling in Sensor Network Games
12:00-1:30 lunch
1:30-2:25 Fan Chung
The combinatorics of PageRank (also an invited WAW talk)
WAW continues