Workshop on Computation and Phase Transitions
June 4-7, 2012 at Georgia Tech

 

Workshop Program

Monday June 4

9:00-9:30	Coffee, refreshments and registration
9:30-10:10	Amin Coja-Oghlan: Catching the k-NAESAT Threshold
10:15-10:45	break
10:45-11:25	Dimitris Achlioptas: Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
11:30-12:00	Alexandre Stauffer: Phase transitions in the detection of a target by mobile nodes
12:00-2:00	catered lunch
2:00-2:40	Fabio Martinelli: Glauber dynamics for constrained spin models on trees
2:45-3:15	Ricardo Restrepo: Improved mixing condition for counting and sampling independent sets
3:20-4:00	break
4:00-4:40	Yin Yitong:  Correlation Decay up to Uniqueness in Spin Systems

Tuesday June 5

9:30-10:10	Allan Sly: The complexity of counting for anti-ferromagnetic 2-spin systems
10:15-10:45	break
10:45-11:15	Andreas Galanis: Inapproximability of the antiferromagnetic Ising model in Two Moments
11:20-11:50	Nike Sun: Potts models on d-regular graphs
11:50-2:15	lunch on own
2:15-2:55	Eyal Lubetzky: The (2+1)-dimensional SOS model: limiting shape and dynamics
3:00-3:40	David Galvin: Proper q-colourings of the cube
3:45-4:30	break
4:30-5:10	David Gamarnik: On the uniqueness of Lebesgue measure on regular trees and the problem of computing the volume of a polytope
6:00	Evening excursion to the GaTech observatory to view the Transit of Venus

Wednesday, June 6  

9:30-10:10	Yuval Peres: Can extra updates delay mixing?
10:15-10:45	break
10:45-11:25	Mike Molloy: Frozen vertices in colourings of a random graph
11:30-12:00	Charliaos Efthymiou: A simple algorithm for random colouring G(n,d/n) using (2+\epsilon)d colours
12:00-2:00	catered lunch
2:00-2:40	Alistair Sinclair: Permanents, Determinants and Commutativity
2:45-3:15	Sarah Miracle: Mixing Times of Self-Organizing Lists and Biased Permutations
3:20-4:00	break
4:00-5:00	Open problem session / discussion:
	Cris Moore: Rational marginals and maximal independent sets

Thursday, June 7  

9:30-10:10	Mark Jerrum: Log-supermodular functions, functional clones and counting CSPs
10:15-10:45	break
10:45-11:25	Ravi Montenegro: A simple heuristic for precisely determining complexity of many Birthday attacks
11:30-12:00	Perla Sousi: Mixing times are hitting times of large sets
12:00-2:15	lunch
2:15-2:55	Tom Hayes: Fractional Independent Sets in Random Graphs
3:00-3:30	Karthekeyan Chandrasekaran: Phase Transition in Random Integer Programs
3:30-4:00	break/end/discussion