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:Isaac Newton Institute Seminar Series
SUMMARY:Expansion of small sets in graphs - Raghavendra\,
P (Georgia Tech)
DTSTART;TZID=Europe/London:20110331T153000
DTEND;TZID=Europe/London:20110331T163000
UID:TALK30496AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/30496
DESCRIPTION:A small set expander is a graph where every set of
sufficiently small size has near perfect edge exp
ansion. This talk concerns the computational prob
lem of distinguishing a small set-expander\, from
a graph containing a small non-expanding set of ve
rtices. This problem henceforth referred to as th
e Small-Set Expansion problem has proven to be int
imately connected to the complexity of large class
es of combinatorial optimization problems. More p
recisely\, the small set expansion problem can be
shown to be directly related to the well-known Uni
que Games Conjecture -- a conjecture that has nume
rous implications in approximation algorithms.\n\n
In this talk\, we motivate the problem\, and surve
y recent work consisting of algorithms and interes
ting connections within graph expansion\, and its
relation to Unique Games Conjecture.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR