DIMACS Workshop on Phase Transitions in Random Structures and Algorithms

March 19 - 23, 2007
Klaus Advanced Computing Building
Klaus Main Auditorium, room 1443
Georgia Institute of Technology

Organizers:

Gregory Sorkin, IBM Research, sorkin@watson.ibm.com

Eric Vigoda, Georgia Institute of Technology, vigoda@cc.gatech.edu

Workshop Program:

Monday, March 19, 2007

 9:30 - 10:05  Inapproximability of the Tutte polynomial 
               Mark Jerrum, Queen Mary

10:10 - 10:45  The Complexity of Weighted Boolean #CSP Coffee break 
               Leslie Goldberg, University of Liverpool

10:45 - 11:30  Break

11:30 - 12:05  Markov Models on Trees: Reconstruction and Applications
               Sebastien Roch, UC Berkeley

12:05 -  2:00  Lunch

 2:00 - 2:35   Monomer-dimer model and a new deterministic approximation 
               algorithm for computing a permanent of a 0,1 matrix
               David Gamarnik, MIT

 2:40 - 3:15   The correlation decay (CD) tree and spatial mixing in multispin systems
               Chandra Nair

 3:15 -  4:00  Break

 4:00 -  4:35  Randomly coloring planar graphs with fewer colors than the maximum degree
               Juan Vera, Georgia Tech

Tuesday, March 20, 2007

 9:30 - 10:05  Convergent Dense Graph Sequences 
               Jennifer Chayes, Microsoft Research

10:10 - 11:10  Percolation on sequences of dense graphs
               Béla Bollobás, Cambridge University and University of Memphis

11:10 - 11:45  Break 

11:45 - 12:20  Monotonicity and Resilience of random graphs
               Van Vu, Rutgers

12:20 -  2:30  Lunch

 2:15 -  2:50  First to Market is not Everything: Phase Transitions 
               in Preferential Attachment with Fitness 
               Christian Borgs, Microsoft Research

 2:55 -  3:30  On a random graph evolving by degrees
               Boris Pittel, Ohio State University
 
 4:00 -  4:15  Sprinkling and the Giant Component 
               Joel Spencer, NYU

 4:20 - 4:55   Expansion and lack thereof in randomly perturbed graphs
               Abie Flaxman, Microsoft Research

Wednesday, March 21, 2007

 9:30 - 10:30  Survey: Belief Propagation, Cavity Method and
               Pure Gibbs States in Combinatorial Problems
               Andrea Montanari, Stanford

10:30 - 11:00  Break

11:00 - 11:35  Clustering and pairs of solutions in random Boolean problems
               Thierry Mora, Université Paris-Sud

11:40 - 12:15  Mixing and clustering in message-passing schemes: A Gibbs measure view
               Sekhar Tatikonda, Yale

12:15 -  2:15  Break

 2:15 -  2:50  On the solution space geometry of random CSPs
               Dimitris Achlioptas, UC Santa Cruz

 2:55 -  3:30  Interpolation inequalities and self-averaging 
               identities in Random k-Sat and other spin systems
               Silvio Franz

Thursday, March 22, 2007

 9:30 - 10:05  Anomalous heat kernel decay for random walk among random conductances<
               Marek Biskup, UCLA

10:10 - 10:45  Coordinate Percolation
               Peter Winkler, Dartmouth

10:45 - 11:30  Break

11:30 - 12:05  Stochastic domination and the Ising model
               Jeffrey Steif, Chalmers

12:05 -  2:00  Break

 2:00 -  2:35  Local limit theorems for the giant component
               Amin Coja-Oghlan, Humboldt University

 2:40 -  3:15  The cover time of random graphs
               Alan Frieze, CMU

 3:15 -  4:00  Break

 4:00 -  4:35  Critical random graphs: diameter and mixing time
               Yuval Peres, Microsoft Research and UC Berkeley

Friday, March 23, 2007

 9:30 - 10:05  The Complexity of Volume Computation: Annealing vs Dispersion
               Santosh Vempala, Georgia Tech

10:10 - 10:45  Dispersion of Mass and Lower Bounds for Randomized Algorithms
               Luis Rademacher, MIT

10:45 - 11:30  Break

11:30 - 12:05  Adaptive Annealing: A Near-optimal Connection between 
               Sampling and Counting
               Daniel Stefankovic, University of Rochester

12:05 -  1:30  Break

 1:30 -  2:05  Random walks for the discrete log problem
               Prasad Tetali, Georgia Tech

 2:10 -  2:45  Evolving a peer-to-peer network
               Martin Dyer

Previous: Participation

Workshop Index

DIMACS Homepage