Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR21-042 | 16th March 2021 00:11

Strong Parallel Repetition for Unique Games on Small Set Expanders

RSS-Feed




TR21-042
Authors: Dana Moshkovitz
Publication: 16th March 2021 00:30
Downloads: 215
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint