# 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 language English (US) Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 443-452 10 https://doi.org/10.1109/FOCS.2011.78 Published - Dec 1 2011 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United StatesDuration: Oct 22 2011 → Oct 25 2011

### Publication series

Name Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 0272-5428

### Other

Other 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 United States Palm Springs, CA 10/22/11 → 10/25/11

## ASJC Scopus subject areas

• Computer Science(all)

## Fingerprint

Dive into the research topics of 'How to play unique games against a semi-random adversary: Study of semi-random models of unique games'. Together they form a unique fingerprint.