Testing for Concise Representations

Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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.
Original languageEnglish
Title of host publication48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings
Pages549-558
Number of pages10
DOIs
Publication statusPublished - 2007

Fingerprint

Dive into the research topics of 'Testing for Concise Representations'. Together they form a unique fingerprint.

Cite this