How to play Unique Games against a Semi-Random adversary

April 13, 2011
Alexandra Kolla | Microsoft Research

We study the average case complexity of the Unique Games problem. We propose a semi-random model, in which a unique game instance is generated in several steps. First an adversary selects a completely satisfiable 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 adversary can obtain any (1-epsilon)-satisfiable instance, so then the 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 polynomial-time if at least one step is random (we require that the average degree of the graph is at least log k).

Joint work with Konstantin Makarychev and Yury Makarychev.

Speaker Details

Alexandra Kolla is a postdoc at MSR in Redmond. Before that, she was a postdoc at the Institute for Advanced Study. She got her PhD at U.C. Berkeley under the supervision of Umesh Vazirani. Her interests lie in the intersection of algorithms and complexity theory.