Document Open Access Logo

On Local Testability in the Non-Signaling Setting

Authors Alessandro Chiesa, Peter Manohar, Igor Shinkar

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2020.26.pdf
  • Filesize: 0.7 MB
  • 37 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • non-signaling strategies
  • locally testable codes
  • low-degree testing
  • Fourier analysis

Metrics

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

Abstract

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics for decades, and have recently found applications in theoretical computer science. These applications motivate the study of local-to-global phenomena for non-signaling functions.
We prove that low-degree testing in the non-signaling setting is possible, assuming that the locality of the non-signaling function exceeds a threshold. We additionally show that if the locality is below the threshold then the test fails spectacularly, in that there exists a non-signaling function which passes the test with probability 1 and yet is maximally far from being low-degree.
Along the way, we present general results about the local testability of linear codes in the non-signaling setting. These include formulating natural definitions that capture the condition that a non-signaling function "belongs" to a given code, and characterizing the sets of local constraints that imply membership in the code. We prove these results by formulating a logical inference system for linear constraints on non-signaling functions that is complete and sound.

Cite As Get BibTex

Alessandro Chiesa, Peter Manohar, and Igor Shinkar. On Local Testability in the Non-Signaling Setting. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 26:1-26:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ITCS.2020.26

Author Details

Alessandro Chiesa
  • UC Berkeley, CA, USA
Peter Manohar
  • Carnegie Mellon University, Pittsburgh, PA, USA
Igor Shinkar
  • Simon Fraser University, Burnaby, Canada

Funding

  • Chiesa, Alessandro: Ethereum Foundation and the Interchain Foundation
  • Manohar, Peter: NSF Graduate Research Fellowship Program (under Grant No. DGE1745016); and the ARCS Foundation. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
  • Shinkar, Igor: NSERC Discovery Grant

Acknowledgements

We are grateful to Thomas Vidick for suggesting using irreducible curves to extend our initial non-testability result for axis-parallel lines to the case of general lines.

References

  1. Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. New Journal of Physics, 13(11):113036, 2011. Google Scholar
  2. 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
  3. 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
  4. 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
  5. Alessandro Chiesa, Peter Manohar, and Igor Shinkar. Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference, ITCS '19, pages 25:1-25:17, 2019. Google Scholar
  6. Oded Goldreich and Madhu Sudan. Locally testable codes and PCPs of almost-linear length. Journal of the ACM, 53:558-655, July 2006. Preliminary version in STOC '02. Google Scholar
  7. 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
  8. 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
  9. 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/.
  10. 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
  11. Anand Natarajan and Thomas Vidick. Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. In Proceedings of the 59th IEEE Symposium on Foundations of Computer Science, FOCS '18, pages 731-742, 2018. Google Scholar
  12. Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379-385, 1994. Google Scholar
  13. Prasad Raghavendra and David Steurer. Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, FOCS '09, pages 575-585, 2009. Full version at URL: http://people.eecs.berkeley.edu/~prasad/Files/cspgaps.pdf.
  14. Peter Rastall. Locality, Bell’s theorem, and quantum mechanics. Foundations of Physics, 15(9):963-972, 1985. Google Scholar
  15. Ronitt Rubinfeld and Madhu Sudan. Robust Characterizations of Polynomials with Applications to Program Testing. SIAM Journal on Computing, 25(2):252-271, 1996. Google Scholar
  16. 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
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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