(2020). Reduction From Non-Unique Games to Boolean Unique Games. The Simons Institute for the Theory of Computing. https://simons.berkeley.edu/talks/reduction-non-unique-games-boolean-unique-games
MLA
Reduction From Non-Unique Games to Boolean Unique Games. The Simons Institute for the Theory of Computing, Dec. 14, 2020, https://simons.berkeley.edu/talks/reduction-non-unique-games-boolean-unique-games
BibTex
@misc{ scivideos_16862,
doi = {},
url = {https://simons.berkeley.edu/talks/reduction-non-unique-games-boolean-unique-games},
author = {},
keywords = {},
language = {en},
title = {Reduction From Non-Unique Games to Boolean Unique Games},
publisher = {The Simons Institute for the Theory of Computing},
year = {2020},
month = {dec},
note = {16862 see, \url{https://scivideos.org/index.php/Simons-Institute/16862}}
}
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 a candidate reduction (i.e., without a proof of soundness). The current work is the first to provide a 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, tight, local testing theorem for the low degree part of functions f:R^n-->R in Gaussian space: We show that the low degree part of the restriction of f to a random hyperplane h is extremely close (O(1/n) Euclidean distance) to the restriction of the low degree part of f to h with high probability.
This is joint work with Ronen Eldan from the Weizmann Institute.