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:Optimization and Incentives Seminar
SUMMARY:Algorithmic Barriers from Phase Transitions - Dimi
tris Achlioptas (University of Athens &\; RACTI
)
DTSTART;TZID=Europe/London:20111122T163000
DTEND;TZID=Europe/London:20111122T173000
UID:TALK34730AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/34730
DESCRIPTION:This talk is cross-listed from the Probability ser
ies\, because it should be of interest to this sem
inar as well.\n\nFor many random optimization prob
lems we have by now very sharp estimates of the sa
tisfiable regime. At the same time\, though\, all
known polynomial-time algorithms only find solutio
ns in a very small fraction of that regime. We stu
dy this phenomenon by examining how the statistics
of the geometry of the set of solutions evolve as
constraints are added. We prove in a precise math
ematical sense that\, for each problem studied\, t
he barrier faced by algorithms corresponds to a ph
ase transition in that problem?s solution-space ge
ometry. Roughly speaking\, at some problem-specifi
c critical density\, the set of solutions shatters
and goes from being a single giant ball to expone
ntially many\, well-separated\, tiny pieces. All k
nown polynomial-time algorithms work in the ball r
egime\, but stop as soon as the shattering occurs.
Besides giving a geometric view of the solution s
pace of random optimization problems our results e
stablish rigorously a substantial part of the 1-st
ep Replica Symmetry Breaking picture of statistica
l physics for these problems.
LOCATION:MR12\, Centre for Mathematical Sciences\, Wilberfo
rce Road\, Cambridge
CONTACT:Elena Yudovina
END:VEVENT
END:VCALENDAR