License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.25
URN: urn:nbn:de:0030-drops-101188
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10118/
Go to the corresponding LIPIcs Volume Portal

Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing

pdf-format:
LIPIcs-ITCS-2019-25.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{chiesa_et_al:LIPIcs:2018:10118,
  author =	{Alessandro Chiesa and Peter Manohar and Igor Shinkar},
  title =	{{Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10118},
  URN =		{urn:nbn:de:0030-drops-101188},
  doi =		{10.4230/LIPIcs.ITCS.2019.25},
  annote =	{Keywords: probabilistically checkable proofs, linearity testing, non-signaling strategies}
}

Keywords: probabilistically checkable proofs, linearity testing, non-signaling strategies
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI