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:TALK33594@talks.cam.ac.uk
CONTACT:HoD Secretary\, DPMMS
DESCRIPTION:\n For many random optimization problems we have by now very s
 harp\nestimates of the satisfiable regime. At the same time\, though\, all
  known\npolynomial-time algorithms only find solutions in a very small fra
 ction of\nthat regime. We study this phenomenon by examining how the stati
 stics of the\ngeometry of the set of solutions evolve as constraints are a
 dded. We prove\nin a precise mathematical sense that\, for each problem st
 udied\, the barrier\nfaced by algorithms corresponds to a phase transition
  in that problem?s\nsolution-space geometry. Roughly speaking\, at some pr
 oblem-specific critical\ndensity\, the set of solutions shatters and goes 
 from being a single giant\nball to exponentially many\, well-separated\, t
 iny pieces. All known\npolynomial-time algorithms work in the ball regime\
 , but stop as soon as the\nshattering occurs. Besides giving a geometric v
 iew of the solution space of\nrandom optimization problems our results est
 ablish rigorously a substantial\npart of the 1-step Replica Symmetry Break
 ing picture of statistical physics\nfor these problems.\n
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0WB
END:VEVENT
END:VCALENDAR