Reduction From Non-Unique Games to Boolean Unique Games

          @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/Simons-Institute/16862}}
          }
          

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.