CS Theory Seminar

Thursday October 19, 2017 3:00 PM

Testing Linearity against No-Signaling Strategies

Speaker: Peter Manohar, UC Berkeley
Location: Annenberg 314

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).

Series Theory of Computing Seminar Series

Contact: Bonnie Leung at 626-395-4964 bjleung@caltech.edu