BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Expansion of small sets in graphs - Raghavendra\, P (Georgia Tech)
DTSTART:20110331T143000Z
DTEND:20110331T153000Z
UID:TALK30496@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:A small set expander is a graph where every set of sufficientl
 y small size has near perfect edge expansion.  This talk concerns the comp
 utational problem of distinguishing a small set-expander\, from a graph co
 ntaining a small non-expanding set of vertices.  This problem henceforth r
 eferred to as the Small-Set Expansion problem has proven to be intimately 
 connected to the complexity of large classes of combinatorial optimization
  problems.  More precisely\, the small set expansion problem can be shown 
 to be directly related to the well-known Unique Games Conjecture -- a conj
 ecture that has numerous implications in approximation algorithms.\n\nIn t
 his talk\, we motivate the problem\, and survey recent work consisting of 
 algorithms and interesting connections within graph expansion\, and its re
 lation to Unique Games Conjecture.\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR