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

Alexandra Kolla, Konstantin Makarychev, Yury Makarychev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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

Original languageEnglish (US)
Title of host publicationProceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
Pages443-452
Number of pages10
DOIs
StatePublished - Dec 1 2011
Event2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States
Duration: Oct 22 2011Oct 25 2011

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011
CountryUnited States
CityPalm Springs, CA
Period10/22/1110/25/11

    Fingerprint

ASJC Scopus subject areas

  • Computer Science(all)

Cite this

Kolla, A., Makarychev, K., & Makarychev, Y. (2011). How to play unique games against a semi-random adversary: Study of semi-random models of unique games. In Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 (pp. 443-452). [6108205] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2011.78