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.2020.26
URN: urn:nbn:de:0030-drops-117112
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11711/
Chiesa, Alessandro ;
Manohar, Peter ;
Shinkar, Igor
On Local Testability in the Non-Signaling Setting
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.
BibTeX - Entry
@InProceedings{chiesa_et_al:LIPIcs:2020:11711,
author = {Alessandro Chiesa and Peter Manohar and Igor Shinkar},
title = {{On Local Testability in the Non-Signaling Setting}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {26:1--26:37},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11711},
URN = {urn:nbn:de:0030-drops-117112},
doi = {10.4230/LIPIcs.ITCS.2020.26},
annote = {Keywords: non-signaling strategies, locally testable codes, low-degree testing, Fourier analysis}
}
Keywords: |
|
non-signaling strategies, locally testable codes, low-degree testing, Fourier analysis |
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
06.01.2020 |