Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-093 | 8th July 2021 18:28

Reduction From Non-Unique Games To Boolean Unique Games

RSS-Feed




Revision #1
Authors: Ronen Eldan, Dana Moshkovitz
Accepted on: 8th July 2021 18:28
Downloads: 306
Keywords: 


Abstract:

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.
In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., without a proof of soundness).
The current work is the first to provide an efficient reduction along with a proof of soundness.
The non-unique game we reduce from is similar to non-unique games for which PCP theorems are known.
Our proof relies on a new concentration theorem for functions in Gaussian space that are restricted to a random hyperplane. We bound the typical Euclidean distance between the low degree part of the restriction of the function to the hyperplane and the restriction to the hyperplane of the low degree part of the function.



Changes to previous version:

Minor edits plus additions to the introduction


Paper:

TR20-093 | 23rd June 2020 17:20

Reduction From Non-Unique Games To Boolean Unique Games





TR20-093
Authors: Ronen Eldan, Dana Moshkovitz
Publication: 23rd June 2020 17:41
Downloads: 661
Keywords: 


Abstract:

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.
In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., without a proof of soundness).
The current work is the first to provide an efficient reduction along with a proof of soundness.
The non-unique game we reduce from is similar to non-unique games for which PCP theorems are known.
Our proof relies on a new concentration theorem for functions in Gaussian space that are restricted to a random hyperplane. We bound the typical Euclidean distance between the low degree part of the restriction of the function to the hyperplane and the restriction to the hyperplane of the low degree part of the function.



ISSN 1433-8092 | Imprint