2026-07-23T20:09:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11711 2024-03-06T10:48:31Z ddc:004 open_access

On Local Testability in the Non-Signaling Setting Chiesa, Alessandro Manohar, Peter Shinkar, Igor non-signaling strategies locally testable codes low-degree testing Fourier analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alessandro Chiesa and Peter Manohar and Igor Shinkar 2020 Is Part Of LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2020.26 urn:nbn:de:0030-drops-117112 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.26 eng https://creativecommons.org/licenses/by/3.0/legalcode