Testing for Concise Representations.
I. Diakonikolas and H. Lee and K. Matulef and K. Onak and R. Rubinfeld and R. Servedio and A. Wan.
48th Symposium on Foundations of Computer Science (FOCS) , 2007, pp. 549--558.


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 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 \etal to work for non-Boolean functions, and give poly$(s/\eps)$-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 a $\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.

Postscript or pdf of full version

Back to main papers page