Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Transactions on Computation Theory

Testing Linearity against Non-signaling Strategies

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Published Jun 1, 2020• 1 citation
Publisher

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.

DOI
10.1145/3397474

Related papers

Testing Linearity against Non-Signaling Strategies

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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.

Leibniz international proceedings in informatics•Jan 1, 2018•0 citations

Testing linearity against non-signaling strategies

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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.

•Jun 22, 2018•3 citations

On Local Testability in the Non-Signaling Setting

Alessandro Chiesa, Peter Manohar, Igor Shinkar

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.

Leibniz international proceedings in informatics•Jan 1, 2020•1 citation

Toward Probabilistic Checking against Non-Signaling Strategies with Constant Locality

Mohammad Mahdi Jahanara, Sajin Koroth, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.

arXiv:2009.04892•Sep 10, 2020•2 citations

Measuring Bell non-locality in the presence of signaling

Mark Broom, Talel Naccache, Emmanuel M. Pothos +2 more

Scientific inquiry seeks causal explanations of observed phenomena. The Bell experiment provides a paradigmatic case, revealing correlations between spatially separated systems that no local model can reproduce. Such correlations, known as Bell non-locality, are typically analyzed under the non-signaling assumption, which requires that local statistics be independent of distant measurement choices. Yet real experiments, as well as applications beyond physics, often involve signaling, raising the question of how non-locality should be characterized without this constraint. We introduce a general method for quantifying Bell non-locality in the presence of signaling, designed to relax locality as little as necessary. Our approach is guided by the question: how often can locality be preserved across repeated trials in explaining the observed correlations? The task reduces to finding the optimal convex decomposition of the observed correlations into local and genuinely non-local components. We solve this problem within the linear-programming framework, obtaining a closed-form solution valid for arbitrary correlations. We further evaluate a corresponding measure of signaling, demonstrating the generality of the method and the non-trivial character of the results. By extending the notion of non-locality beyond the non-signaling regime, our framework reshapes the basis for experimental analysis in physics and offers tools applicable outside physics.

quant-pharXiv:2603.00984•New Journal of Physics•Mar 3, 2026•0 citations

Probabilistic Checking Against Non-Signaling Strategies from Linearity Testing

Alessandro Chiesa, Peter Manohar, Igor Shinkar

Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proofs (PCPs) that are sound against non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.

Leibniz international proceedings in informatics•Jan 1, 2019•3 citations
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.
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.
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.
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.
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proof (PCPs) systems that are sound against non-signaling strategies. In this paper we show, assuming a certain geometrical hypothesis about noise robustness of non-signaling proofs (or, equivalently, about robustness to noise of solutions to the Sherali-Adams linear program), that a slight variant of the parallel repetition of the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies with constant locality. Our proof relies on the analysis of the linearity test and agreement test (also known as the direct product test) in the non-signaling setting.
Scientific inquiry seeks causal explanations of observed phenomena. The Bell experiment provides a paradigmatic case, revealing correlations between spatially separated systems that no local model can reproduce. Such correlations, known as Bell non-locality, are typically analyzed under the non-signaling assumption, which requires that local statistics be independent of distant measurement choices. Yet real experiments, as well as applications beyond physics, often involve signaling, raising the question of how non-locality should be characterized without this constraint. We introduce a general method for quantifying Bell non-locality in the presence of signaling, designed to relax locality as little as necessary. Our approach is guided by the question: how often can locality be preserved across repeated trials in explaining the observed correlations? The task reduces to finding the optimal convex decomposition of the observed correlations into local and genuinely non-local components. We solve this problem within the linear-programming framework, obtaining a closed-form solution valid for arbitrary correlations. We further evaluate a corresponding measure of signaling, demonstrating the generality of the method and the non-trivial character of the results. By extending the notion of non-locality beyond the non-signaling regime, our framework reshapes the basis for experimental analysis in physics and offers tools applicable outside physics.
Non-signaling strategies are a generalization of quantum strategies that have been studied in physics over the past three decades. Recently, they have found applications in theoretical computer science, including to proving inapproximability results for linear programming and to constructing protocols for delegating computation. A central tool for these applications is probabilistically checkable proofs (PCPs) that are sound against non-signaling strategies. In this paper we prove that the exponential-length constant-query PCP construction due to Arora et al. (JACM 1998) is sound against non-signaling strategies. Our result offers a new length-vs-query tradeoff when compared to the non-signaling PCP of Kalai, Raz, and Rothblum (STOC 2013 and 2014) and, moreover, may serve as an intermediate step to a proof of a non-signaling analogue of the PCP Theorem.