BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Algorithmic Barriers from Phase Transitions - Dimitris Achlioptas 
 (University of Athens &amp\; RACTI)
DTSTART:20111122T163000Z
DTEND:20111122T173000Z
UID:TALK34730@talks.cam.ac.uk
CONTACT:Elena Yudovina
DESCRIPTION:This talk is cross-listed from the Probability series\, becaus
 e it should be of interest to this seminar as well.\n\nFor many random opt
 imization problems we have by now very sharp estimates of the satisfiable 
 regime. At the same time\, though\, all known polynomial-time algorithms o
 nly find solutions in a very small fraction of that regime. We study this 
 phenomenon by examining how the statistics of the geometry of the set of s
 olutions evolve as constraints are added. We prove in a precise mathematic
 al sense that\, for each problem studied\, the barrier faced by algorithms
  corresponds to a phase transition in that problem?s solution-space geomet
 ry. Roughly speaking\, at some problem-specific critical density\, the set
  of solutions shatters and goes from being a single giant ball to exponent
 ially many\, well-separated\, tiny pieces. All known polynomial-time algor
 ithms work in the ball regime\, but stop as soon as the shattering occurs.
  Besides giving a geometric view of the solution space of random optimizat
 ion problems our results establish rigorously a substantial part of the 1-
 step Replica Symmetry Breaking picture of statistical physics for these pr
 oblems.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberforce Road\, Camb
 ridge
END:VEVENT
END:VCALENDAR