How to play Unique Games against a Semi-Random adversary

Опубликовано 17 августа 2016, 1:22

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.