文章基本信息

标题：Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing
本地全文：下载
作者：Alessandro Chiesa ; Peter Manohar ; Igor Shinkar 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：124
页码：1-17
DOI：10.4230/LIPIcs.ITCS.2019.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 proofs (PCPs) that are sound against non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.
关键词：probabilistically checkable proofs; linearity testing; non-signaling strategies