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

Monday, March 19, 20079: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 TechTuesday, March 20, 20079: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 ResearchWednesday, March 21, 20079: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 FranzThursday, March 22, 20079: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 BerkeleyFriday, March 23, 20079: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

Contacting the Center

Document last modified on March 14, 2007.