Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-045 | 2nd July 2012 18:05

Property Testing Lower Bounds via Communication Complexity

RSS-Feed




Revision #1
Authors: Eric Blais, Joshua Brody, Kevin Matulef
Accepted on: 2nd July 2012 18:05
Downloads: 7307
Keywords: 


Abstract:

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds.

For the problem of testing whether a boolean function is $k$-linear (a parity function on $k$ variables), we achieve a lower bound of $\Omega(k)$ queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010). The same argument behind this lower bound also implies a new proof of known lower bounds for testing related classes such as $k$-juntas. For some classes, such as the class of monotone functions and the class of $s$-sparse GF(2) polynomials, we significantly strengthen the best known bounds.



Changes to previous version:

Journal version of the paper. Appears in Computational Complexity 21(2), 2012.


Paper:

TR11-045 | 1st April 2011 16:22

Property Testing Lower Bounds via Communication Complexity





TR11-045
Authors: Eric Blais, Joshua Brody, Kevin Matulef
Publication: 1st April 2011 20:26
Downloads: 3406
Keywords: 


Abstract:

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in testing. This scheme is general and implies a number of new testing bounds, as well as simpler proofs of several known bounds.

For the problem of testing whether a boolean function is $k$-linear (a parity function on $k$ variables), we achieve a lower bound of $\Omega(k)$ queries, even for adaptive algorithms with two-sided error, thus confirming a conjecture of Goldreich (2010). The same argument behind this lower bound also implies a new proof of known lower bounds for testing related classes such as $k$-juntas. For some classes, such as the class of monotone functions and the class of $s$-sparse GF(2) polynomials, we significantly strengthen the best known bounds.



ISSN 1433-8092 | Imprint