Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > RONEN ELDAN:
All reports by Author Ronen Eldan:

TR20-093 | 23rd June 2020
Ronen Eldan, Dana Moshkovitz

Reduction From Non-Unique Games To Boolean Unique Games

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., ... more >>>




ISSN 1433-8092 | Imprint