论文标题
朝着概率检查持续位置的非信号策略
Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality
论文作者
论文摘要
非信号策略是对过去三十年中物理学研究的量子策略的概括。最近，他们发现了理论计算机科学中的应用程序，包括证明线性编程的不合适性结果以及构建用于委派计算的协议。这些应用程序的中心工具是概率可检查的证明（PCP）系统，这些系统是针对非信号策略的声音。 在本文中，我们表明，假设对非信号证明的噪声鲁棒性有一定的几何假设（或等效地，关于sherali-Adams线性程序的溶液噪声的鲁棒性），这是由于Arora等人归因于Arora et al al Arora et al al al al al al al al a arora et al a al n o n a sheri-adams线性程序的稳健性。 （JACM 1998）声音是反对具有持续位置的非信号策略的声音。 我们的证明依赖于在非信号设置中的线性测试和协议测试（也称为直接产品测试）的分析。
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.
