{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T21:16:48Z","timestamp":1757452608703,"version":"3.41.0"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T00:00:00Z","timestamp":1590969600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2020,9,30]]},"abstract":"<jats:p>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\u2019s apparent non-locality. Recently, they have received attention in theoretical computer science due to connections to Complexity and Cryptography.<\/jats:p>\n          <jats:p>\n            We initiate the study of Property Testing against non-signaling strategies, focusing first on the classical problem of\n            <jats:italic>linearity testing<\/jats:italic>\n            (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\n            <jats:italic>quasi-distribution<\/jats:italic>\n            over linear functions.\n          <\/jats:p>\n          <jats:p>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 \u201clocal views\u201d 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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3397474","type":"journal-article","created":{"date-parts":[[2020,6,1]],"date-time":"2020-06-01T10:13:38Z","timestamp":1591006418000},"page":"1-51","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Testing Linearity against Non-signaling Strategies"],"prefix":"10.1145","volume":"12","author":[{"given":"Alessandro","family":"Chiesa","sequence":"first","affiliation":[{"name":"UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Manohar","sequence":"additional","affiliation":[{"name":"UC Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Igor","family":"Shinkar","sequence":"additional","affiliation":[{"name":"Simon Fraser University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/13\/11\/113036"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_39"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.111.170403"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0025-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103428"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.75.032304"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.010503"},{"key":"e_1_2_1_11_1","first-page":"022101","article-title":"Nonlocal correlations as an information-theoretic resource","volume":"71","author":"Barrett Jonathan","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.140401"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1323937.1323942"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.54"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.96.250401"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.08.035"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2006.1663"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.220403"},{"volume-title":"Reichardt","year":"2017","author":"Chao Rui","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1061655"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1098\/rspa.1942.0023","article-title":"The physical interpretation of quantum mechanics","volume":"180","author":"Dirac Paul A. M.","year":"1942","journal-title":"Proc. Roy. Soc. Lond. A: Math., Phys Eng. Sci."},{"key":"e_1_2_1_24_1","unstructured":"Cynthia Dwork Michael Langberg Moni Naor Kobbi Nissim and Omer Reingold. 2004. Succinct NP Proofs and Spooky Interactions. Retrieved from www.openu.ac.il\/home\/mikel\/papers\/spooky.ps.  Cynthia Dwork Michael Langberg Moni Naor Kobbi Nissim and Omer Reingold. 2004. Succinct NP Proofs and Spooky Interactions. Retrieved from www.openu.ac.il\/home\/mikel\/papers\/spooky.ps."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226652"},{"key":"e_1_2_1_26_1","unstructured":"Richard P. Feynman. 1987. Negative probability. In Quantum Implications: Essays in Honour of David Bohm Basil J. Hiley and D. Peat (Eds.). 235--248.  Richard P. Feynman. 1987. Negative probability. In Quantum Implications: Essays in Honour of David Bohm Basil J. Hiley and D. Peat (Eds.). 235--248."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a008"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_13"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.22"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.72.052312"},{"volume-title":"Proceedings of the 45th ACM Symposium on the Theory of Computing (STOC\u201913)","year":"2013","author":"Kalai Yael","key":"e_1_2_1_33_1"},{"volume-title":"Proceedings of the 7th Innovations in Theoretical Computer Science Conference (ITCS\u201916)","year":"2016","author":"Kalai Yael Tauman","key":"e_1_2_1_34_1"},{"volume-title":"Proceedings of the 46th ACM Symposium on Theory of Computing (STOC\u201914)","year":"2013","author":"Kalai Yael Tauman","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of the Symposium on the Foundations of Modern Physics","year":"1985","author":"Leonid","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.99.180502"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.012112"},{"volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan","key":"e_1_2_1_40_1"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02058098"},{"volume-title":"Causality and Nonlocality as Axioms for Quantum Mechanics","author":"Popescu Sandu","key":"e_1_2_1_42_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-017-0990-3_45"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.73"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00739036"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793255151"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403036"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-006-0015-4"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.73.012101"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007421"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-012-9353-6"},{"key":"e_1_2_1_53_1","unstructured":"Thomas Vidick. 2014. Linearity testing with entangled provers. Retrieved from http:\/\/users.cms.caltech.edu\/ vidick\/linearity_test.pdf.  Thomas Vidick. 2014. Linearity testing with entangled provers. Retrieved from http:\/\/users.cms.caltech.edu\/ vidick\/linearity_test.pdf."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2005.1523644"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397474","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397474","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:33Z","timestamp":1750200093000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397474"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,9,30]]}},"alternative-id":["10.1145\/3397474"],"URL":"https:\/\/doi.org\/10.1145\/3397474","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2020,6]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}