Conference: The 48th Annual Symposium on Foundations of Computer Science (FOCS 2007).

Abstract: We describe a general method for testing whether a function on $n$
input variables has a concise representation. The approach combines
ideas from the junta test of Fischer *et al.* with ideas
from learning theory, and yields property testers that make
$\operatorname{poly}(s/\epsilon)$ queries (independent of $n$) for Boolean function
classes such as $s$-term DNF formulas
(answering a question posed by Parnas *et al.*),
size-$s$ decision trees, size-$s$ Boolean formulas,
and size-$s$ Boolean circuits.

The method can be applied to non-Boolean valued function classes as
well. This is achieved via a generalization of the notion of
*variation* from Fischer *et al.* to non-Boolean functions. Using
this generalization we extend the original junta test of Fischer
*et al.* to work for non-Boolean functions, and give
$\operatorname{poly}(s/\epsilon)$-query testing algorithms for non-Boolean valued
function classes such as size-$s$ algebraic circuits and $s$-sparse
polynomials over finite fields.

We also prove an $\tilde\Omega(\sqrt{s})$ query lower bound for nonadaptively testing $s$-sparse polynomials over finite fields of constant size. This shows that in some instances, our general method yields a property tester with query complexity that is optimal (for nonadaptive algorithms) up to a polynomial factor.