Select All
16862

Reduction From Non-Unique Games to Boolean Unique Games

APA

(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

Dana Moshkovitz (University of Texas, Austin)
Talk number16862
Source RepositorySimons Institute

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