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

Title of host publication | Proceedings - 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 |

Pages | 443-452 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2011 |

Event | 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011 - Palm Springs, CA, United States Duration: Oct 22 2011 → Oct 25 2011 |

### Other

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

Country/Territory | United States |

City | Palm Springs, CA |

Period | 10/22/11 → 10/25/11 |

## ASJC Scopus subject areas

- Computer Science(all)