CS Theory Seminar

Abstract: No-signaling strategies are collections of distributions with certain non-local correlations. In this talk, we study the classical problem of linearity testing (Blum, Luby, and Rubinfeld; JCSS 1993) against no-signaling strategies. We prove that any no-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 functions by allowing negative probabilities, while at the same time requiring that "local views" follow standard distributions (with non-negative probabilities). As part of our analysis, we also establish a general equivalence between no-signaling strategies and quasi-distributions, which provides a useful perspective on the study of Property Testing against no-signaling strategies beyond linearity testing.
Joint work with Alessandro Chiesa (UC Berkeley) and Igor Shinkar (UC Berkeley).