Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-123 | 15th November 2018 01:36

Probabilistic Checking against Non-Signaling Strategies from Linearity Testing

RSS-Feed




Revision #1
Authors: Alessandro Chiesa, Peter Manohar, Igor Shinkar
Accepted on: 15th November 2018 01:36
Downloads: 831
Keywords: 


Abstract:

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.


Paper:

TR18-123 | 3rd July 2018 21:45

Probabilistic Checking against Non-Signaling Strategies from Linearity Testing





TR18-123
Authors: Alessandro Chiesa, Peter Manohar, Igor Shinkar
Publication: 4th July 2018 03:01
Downloads: 1012
Keywords: 


Abstract:

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 et al. (STOC 2013 and 2014) and, moreover, provides additional evidence to the conjecture that a non-signaling analogue of the PCP Theorem holds



ISSN 1433-8092 | Imprint