Strong Parallel Repetition for Unique Games on Small Set Expanders
The strong parallel repetition problem for unique games is to efficiently reduce the 1-delta vs. 1-C*delta gap problem of Boolean unique games (where C>1 is a sufficiently large constant) to the 1-epsilon vs. epsilon gap problem of unique games over large alphabet.
Due to its importance to the Unique Games Conjecture, this problem garnered a great deal of interest from the research community.
There are positive results for certain easy unique games (e.g., unique games on expanders), and an impossibility result for hard unique games.
In this paper we show how to bypass the impossibility result by enlarging the alphabet sufficiently before repetition.
We consider the case of unique games on small set expanders for two setups: (i) Strong small set expanders that yield easy unique games.
(ii) Weaker small set expanders underlying possibly hard unique games as long as the game is mildly fortified.
We show how to fortify unique games in both cases, i.e., how to transform the game so sufficiently large induced sub-games have bounded value. We then prove strong parallel repetition for the fortified games. Prior to this work fortification was known for projection games but seemed hopeless for unique games.
Added the result for potentially hard unique games. The previous version only had the result for strong small set expanders, but mistakingly claimed that there could be hard unique games on such graphs.
We show that NP-hardness of approximating Boolean unique games on small set expanders can be amplified to the full Unique Games Conjecture on small set expanders.
The latter conjecture is known to imply hardness results for problems like Balanced-Separator, Minimum-Linear-Rearrangement and Small-Set-Expansion that are not known under the Unique Games Conjecture.
Our result follows from: (1) A transformation that fortifies any unique game on a small set expander. (2) An improved parallel repetition theorem for fortified games on small set expanders.
Our approach avoids the known limitation on strong parallel repetition of unique games by enlarging the alphabet considerably before repetition. The limitation does not hold for unique games with a sufficiently large alphabet.
Prior to this work, parallel repetition from fortification was only known for projection games, and seemed hopeless for unique games.
Perhaps surprisingly, the idea for fortification of unique games comes from a reduction of Raghavendra and Steurer from Small-Set-Expansion to Unique Games.
I would like to retract the paper due to a bug in the fortification lemma: The basic idea underlying the paper was that a reduction like Raghavendra-Steurer from small set expansion to unique games introduces a product structure without hurting the completeness error. Hence, like in Raz's proof of the parallel repetition theorem, even conditioning on winning many rounds, a typical additional round approximately simulates the original game. Unfortunately, for a problem like small set expansion one needs to approximately simulate it *conditioned on one of the vertices falling into the small set*. This is not necessarily possible while also conditioning on winning many rounds.
