Document Open Access Logo

Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing

Authors Alessandro Chiesa, Peter Manohar, Igor Shinkar

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2019.25.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Alessandro Chiesa
  • UC Berkeley, Berkeley, CA, USA
Peter Manohar
  • UC Berkeley, Berkeley, CA, USA
Igor Shinkar
  • Simon Fraser University, Vancouver, Canada

Funding

This work was supported by the UC Berkeley Center for Long-Term Cybersecurity.

Cite As Get BibTex

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.25

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • probabilistically checkable proofs
  • linearity testing
  • non-signaling strategies

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, 1998. Preliminary version in FOCS '92. Google Scholar
  2. Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: a new characterization of NP. Journal of the ACM, 45(1):70-122, 1998. Preliminary version in FOCS '92. Google Scholar
  3. László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. Checking computations in polylogarithmic time. In Proceedings of the 23rd ACM Symposium on Theory of Computing, STOC '91, pages 21-32, 1991. Google Scholar
  4. László Babai, Lance Fortnow, and Carsten Lund. Non-Deterministic Exponential Time has Two-Prover Interactive Protocols. Computational Complexity, 1:3-40, 1991. Preliminary version appeared in FOCS '90. Google Scholar
  5. Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory, 42(6):1781-1795, 1996. Google Scholar
  6. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan. Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding. SIAM Journal on Computing, 36(4):889-974, 2006. Google Scholar
  7. Nir Bitansky and Alessandro Chiesa. Succinct Arguments from Multi-Prover Interactive Proofs and their Efficiency Benefits. In Proceedings of the 32nd Annual International Cryptology Conference, CRYPTO '12, pages 255-272, 2012. Google Scholar
  8. Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer and System Sciences, 47(3):549-595, 1993. Google Scholar
  9. Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Testing Linearity against Non-Signaling Strategies. In Proceedings of the 33rd Annual Conference on Computational Complexity, CCC '18, pages 17:1-17:37, 2018. Google Scholar
  10. Irit Dinur and Omer Reingold. Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem. In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, FOCS '04, pages 155-164, 2004. Google Scholar
  11. Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268-292, 1996. Preliminary version in FOCS '91. Google Scholar
  12. Justin Holmgren and Ron Rothblum. Delegation With (Nearly) Optimal Time/Space Overhead. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science, FOCS '18, pages ???-???, 2018. Google Scholar
  13. Tsuyoshi Ito. Polynomial-Space Approximation of No-Signaling Provers. In Proceedings of the 37th International Colloquium on Automata, Languages and Programming, ICALP '10, pages 140-151, 2010. Google Scholar
  14. Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto. Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. In Proceedings of the 24th IEEE Annual Conference on Computational Complexity, CCC '09, pages 217-228, 2009. Google Scholar
  15. Yael Kalai, Ran Raz, and Ron Rothblum. Delegation for Bounded Space. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC '13, pages 565-574, 2013. Google Scholar
  16. Yael Tauman Kalai, Ran Raz, and Oded Regev. On the Space Complexity of Linear Programming with Preprocessing. In Proceedings of the 7th Innovations in Theoretical Computer Science Conference, ITCS '16, pages 293-300, 2016. Google Scholar
  17. Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum. How to delegate computations: the power of no-signaling proofs. In Proceedings of the 46th ACM Symposium on Theory of Computing, STOC '14, pages 485-494, 2014. Full version available at URL: https://eccc.weizmann.ac.il/report/2013/183/.
  18. Leonid A Khalfin and Boris S Tsirelson. Quantum/classical correspondence in the light of Bell’s inequalities. Foundations of physics, 22(7):879-948, 1992. Google Scholar
  19. Joe Kilian. A note on efficient zero-knowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC '92, pages 723-732, 1992. Google Scholar
  20. Susumu Kiyoshima. No-signaling Linear PCPs. In Proceedings of the 16th Theory of Cryptography Conference, TCC '18, pages 67-97, 2018. Google Scholar
  21. Silvio Micali. Computationally Sound Proofs. SIAM Journal on Computing, 30(4):1253-1298, 2000. Preliminary version appeared in FOCS '94. Google Scholar
  22. Omer Paneth and Guy Rothblum. On Zero-Testable Homomorphic Encryption and Publicly Verifiable Non-Interactive Arguments. In Proceedings of the 15th Theory of Cryptography Conference, TCC '17, 2017. Google Scholar
  23. Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379-385, 1994. Google Scholar
  24. Peter Rastall. Locality, Bell’s theorem, and quantum mechanics. Foundations of Physics, 15(9):963-972, 1985. Google Scholar
  25. Hanif D. Sherali and Warren P. Adams. A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems. SIAM Journal on Discrete Mathematics, 3(3):411-430, 1990. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact