How to play unique games against a semi-random adversary: Study of semi-random models of unique games

Abstract

In this paper, 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 ε-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-ε)-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-δ) fraction of all constraints in polynomial-time if at least one step is random (we require that the average degree of the graph is Ω(log k)). Our result holds only for ε less than some absolute constant. We prove that if ε ≥ 1/2, then the problem is hard in one of the models, that is, no polynomial-time algorithm can distinguish between the following two cases: (i) the instance is a (1-ε)-satisfiable semi-random instance and (ii) the instance is at most δ-satisfiable (for every δ > 0); the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-ε)-satisfiable. We present an algorithm that distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1-δ)-satisfiable instances if ε gt; cδ (for some absolute constant c). © 2011 IEEE.