TY - GEN

T1 - How to play unique games against a semi-random adversary

T2 - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

AU - Kolla, Alexandra

AU - Makarychev, Konstantin

AU - Makarychev, Yury

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=84863333300&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863333300&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2011.78

DO - 10.1109/FOCS.2011.78

M3 - Conference contribution

AN - SCOPUS:84863333300

SN - 9780769545714

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 443

EP - 452

BT - Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011

Y2 - 22 October 2011 through 25 October 2011

ER -