BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:How to Play Unique Games Against a Semi-Random Adversary - Makaryc
 hev\, K (IBM Research)
DTSTART:20110524T130000Z
DTEND:20110524T140000Z
UID:TALK31491@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We study the average case complexity of the Unique Games probl
 em. We propose a semi-random model\, in which a unique game instance is ge
 nerated in several steps. First an adversary selects a completely satisfia
 ble instance of Unique Games\, then she chooses an epsilon-fraction of all
  edges\, and finally replaces ("corrupts'') the constraints corresponding 
 to these edges with new constraints. If all steps are adversarial\, the ad
 versary can obtain any (1-epsilon)-satisfiable instance\, so then the prob
 lem is as hard as in the worst case. We show however that we can find a so
 lution satisfying a (1-delta)-fraction of all constraints in polynomial-ti
 me if at least one step is random (we require that the average degree of t
 he graph is at least log k). Our result holds only for epsilon less than s
 ome absolute constant. We prove that if epsilon 1/2\, then the problem is 
 hard\, that is\, no polynomial-time algorithm can distinguish between the 
 following two cases: (i) the instance is a (1-epsilon) satisfiable semi-ra
 ndom instance and (ii) the instance is at most delta satisfiable (for ever
 y delta > 0)\; the result assumes the 2-to-2 Unique Games conjecture.\n \n
 Finally\, we study semi-random instances of Unique Games that are at most 
 (1-epsilon) satisfiable. We present an algorithm that distinguishes betwee
 n the case when the instance is a semi-random instance and the case when t
 he instance is an arbitrary (1-delta)-satisfiable instance (if epsilon > c
  delta\, for some absolute constant c).\n\n Joint work with Alexandra Koll
 a and Yury Makarychev\n \n\n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR