Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



Revision #1 to TR21-042 | 8th July 2021 18:11

Strong Parallel Repetition for Unique Games on Small Set Expanders


Revision #1
Authors: Dana Moshkovitz
Accepted on: 8th July 2021 18:11
Downloads: 177


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.

Changes to previous version:

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.


TR21-042 | 16th March 2021 00:11

Strong Parallel Repetition for Unique Games on Small Set Expanders

Authors: Dana Moshkovitz
Publication: 16th March 2021 00:30
Downloads: 409


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.


Comment #1 to TR21-042 | 25th August 2022 10:58


Authors: Dana Moshkovitz
Accepted on: 25th August 2022 10:58


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.

ISSN 1433-8092 | Imprint