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.CCC.2018.17
URN: urn:nbn:de:0030-drops-88731
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8873/
Go to the corresponding LIPIcs Volume Portal

Chiesa, Alessandro ; Manohar, Peter ; Shinkar, Igor

Testing Linearity against Non-Signaling Strategies

pdf-format:
LIPIcs-CCC-2018-17.pdf (0.7 MB)

Abstract

Non-signaling strategies are collections of distributions with certain non-local correlations. They have been studied in Physics as a strict generalization of quantum strategies to understand the power and limitations of Nature's apparent non-locality. Recently, they have received attention in Theoretical Computer Science due to connections to Complexity and Cryptography.
We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993). We prove that any non-signaling strategy that passes the linearity test with high probability must be close to a quasi-distribution over linear functions.
Quasi-distributions generalize the notion of probability distributions over global objects (such as functions) by allowing negative probabilities, while at the same time requiring that "local views" follow standard distributions (with non-negative probabilities). Quasi-distributions arise naturally in the study of Quantum Mechanics as a tool to describe various non-local phenomena.
Our analysis of the linearity test relies on Fourier analytic techniques applied to quasi-distributions. Along the way, we also establish general equivalences between non-signaling strategies and quasi-distributions, which we believe will provide a useful perspective on the study of Property Testing against non-signaling strategies beyond linearity testing.

BibTeX - Entry

@InProceedings{chiesa_et_al:LIPIcs:2018:8873,
  author =	{Alessandro Chiesa and Peter Manohar and Igor Shinkar},
  title =	{{Testing Linearity against Non-Signaling Strategies}},
  booktitle =	{33rd Computational Complexity Conference (CCC 2018)},
  pages =	{17:1--17:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-069-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{102},
  editor =	{Rocco A. Servedio},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2018/8873},
  URN =		{urn:nbn:de:0030-drops-88731},
  doi =		{10.4230/LIPIcs.CCC.2018.17},
  annote =	{Keywords: property testing, linearity testing, non-signaling strategies, quasi-distributions}
}

Keywords: property testing, linearity testing, non-signaling strategies, quasi-distributions
Collection: 33rd Computational Complexity Conference (CCC 2018)
Issue Date: 2018
Date of publication: 04.06.2018

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