• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Annual Symposium on Foundations of Computer Science >Parallel Repetition from Fortification
【24h】

Parallel Repetition from Fortification

机译：从设防平行重复

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and short. As corollaries, we obtain: (1) Starting from a PCP Theorem with soundness error bounded away from 1, we get a PCP with arbitrarily small constant soundness error. In particular, starting with the combinatorial PCP of Dinur, we get a combinatorial PCP with low error. The latter can be used for hardness of approximation as in the work of Håstad. (2) Starting from the work of the author and Raz, we get a projection PCP theorem with the smallest soundness error known today. The theorem yields nearly a quadratic improvement in the size compared to previous work. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error.
机译：平行重复定理在基础博弈的价值和重复次数方面，将重复的（张紧的）两个证明者博弈的值上限。在这项工作中，我们对游戏进行了简单的转换-“强化”，并表明对于强化游戏，重复游戏的价值随着重复次数的增加而呈指数下降，最大到一个很小的附加误差。我们的证明是组合的和简短的。作为推论，我们得到：（1）从具有1的稳健性误差的PCP定理开始，我们得到具有任意小的恒定稳健性误差的PCP。特别是，从Dinur的组合PCP开始，我们得到了误差低的组合PCP。后者可以像Håstad的工作那样用于近似硬度。 （2）从作者和Raz的工作出发，我们得到了当今已知最小的稳健性误差的投影PCP定理。与以前的工作相比，该定理的大小几乎提高了二次方。然后，我们讨论并行重复非随机化的问题，以及在这种情况下设防思想的局限性。我们指出了将并行重复非随机化的问题与合成的问题之间的联系。这种联系可以揭示所谓的“投影游戏猜想”，它要求以最小的误差进行投影PCP。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号