How to Play Unique Games against a Semi-Random Adversary

Details How to Play Unique Games against a Semi-Random Adversary How to Play Unique Games against a Semi-Random Adversary

2011-04-19

arxiv.org/abs/1104.3806v1

Computer Science

Data Structures and Algorithms

Scientific paper

In this paper, we study the average case complexity of the Unique Games problem. We propose a natural 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 epsilon-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-epsilon) satisfiable instance, so then the problem is as hard as in the worst case. In our semi-random model, one of the steps is random, and all other steps are adversarial. We show that known algorithms for unique games (in particular, all algorithms that use the standard SDP relaxation) fail to solve semi-random instances of Unique Games. We present an algorithm that with high probability finds a solution satisfying a (1-delta) fraction of all constraints in semi-random instances (we require that the average degree of the graph is Omega(log k). To this end, we consider a new non-standard SDP program for Unique Games, which is not a relaxation for the problem, and show how to analyze it. We present a new rounding scheme that simultaneously uses SDP and LP solutions, which we believe is of independent interest. Our result holds only for epsilon less than some absolute constant. We prove that if epsilon > 1/2, then the problem is hard in one of the models, the result assumes the 2-to-2 conjecture. Finally, we study semi-random instances of Unique Games that are at most (1-epsilon) satisfiable. We present an algorithm that with high probability, distinguishes between the case when the instance is a semi-random instance and the case when the instance is an (arbitrary) (1-delta) satisfiable instance if epsilon > c delta.

Affiliated with

Also associated with

No associations

Rating

How to Play Unique Games against a Semi-Random Adversary does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with How to Play Unique Games against a Semi-Random Adversary, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and How to Play Unique Games against a Semi-Random Adversary will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-183691