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:How to Play Unique Games Against a Semi-Random Adv
ersary - Makarychev\, K (IBM Research)
DTSTART;TZID=Europe/London:20110524T140000
DTEND;TZID=Europe/London:20110524T150000
UID:TALK31491AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/31491
DESCRIPTION:We study the average case complexity of the Unique
Games problem. We propose a semi-random model\, i
n which a unique game instance is generated in sev
eral steps. First an adversary selects a completel
y satisfiable instance of Unique Games\, then she
chooses an epsilon-fraction of all edges\, and fin
ally replaces ("corrupts'') the constraints corres
ponding to these edges with new constraints. If al
l steps are adversarial\, the adversary can obtain
any (1-epsilon)-satisfiable instance\, so then th
e problem is as hard as in the worst case. We show
however that we can find a solution satisfying a
(1-delta)-fraction of all constraints in polynomia
l-time if at least one step is random (we require
that the average degree of the graph is at least l
og k). Our result holds only for epsilon less than
some absolute constant. We prove that if epsilon
1/2\, then the problem is hard\, that is\, no poly
nomial-time algorithm can distinguish between the
following two cases: (i) the instance is a (1-epsi
lon) satisfiable semi-random instance and (ii) the
instance is at most delta satisfiable (for every
delta > 0)\; the result assumes the 2-to-2 Unique
Games conjecture.\n \nFinally\, we study semi-rand
om instances of Unique Games that are at most (1-e
psilon) satisfiable. We present an algorithm that
distinguishes between the case when the instance i
s a semi-random instance and the case when the ins
tance is an arbitrary (1-delta)-satisfiable instan
ce (if epsilon > c delta\, for some absolute const
ant c).\n\n Joint work with Alexandra Kolla and Yu
ry Makarychev\n \n\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR