论文标题
从非唯一游戏减少到布尔独特游戏
Reduction From Non-Unique Games To Boolean Unique Games
论文作者
论文摘要
我们将证明“布尔独特游戏猜想”的问题减少了（对于任何C> 1的GAP 1-Delta vs. 1-C*Delta，并且足够小的Delta> 0），以证明为某些非独特游戏证明PCP定理。在先前的工作中，Khot和Moshkovitz提出了降低效率低下的候选人（即没有声音证明）。当前的工作是第一个提供有效降低以及声音证明的工作。我们减少的非唯一游戏类似于已知PCP定理的非唯一游戏。我们的证明依靠一个新的浓度定理用于高斯空间中的功能，该功能仅限于随机超平面。我们将函数限制到超平面的限制和限制与功能低度部分的超平面之间的典型欧几里得距离之间结合。
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.
