BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Probability
SUMMARY:Algorithmic Barriers from Phase Transitions - Dim
itris Achlioptas (University of Athens &\; RACT
I)
DTSTART;TZID=Europe/London:20111122T163000
DTEND;TZID=Europe/London:20111122T173000
UID:TALK33594AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/33594
DESCRIPTION:\n For many random optimization problems we have b
y now very sharp\nestimates of the satisfiable reg
ime. At the same time\, though\, all known\npolyno
mial-time algorithms only find solutions in a very
small fraction of\nthat regime. We study this phe
nomenon by examining how the statistics of the\nge
ometry of the set of solutions evolve as constrain
ts are added. We prove\nin a precise mathematical
sense that\, for each problem studied\, the barrie
r\nfaced by algorithms corresponds to a phase tran
sition in that problem?s\nsolution-space geometry.
Roughly speaking\, at some problem-specific criti
cal\ndensity\, the set of solutions shatters and g
oes from being a single giant\nball to exponential
ly many\, well-separated\, tiny pieces. All known\
npolynomial-time algorithms work in the ball regim
e\, but stop as soon as the\nshattering occurs. Be
sides giving a geometric view of the solution spac
e of\nrandom optimization problems our results est
ablish rigorously a substantial\npart of the 1-ste
p Replica Symmetry Breaking picture of statistical
physics\nfor these problems.\n
LOCATION:MR12\, CMS\, Wilberforce Road\, Cambridge\, CB3 0W
B
CONTACT:HoD Secretary\, DPMMS
END:VEVENT
END:VCALENDAR