ECCC-Report TR07-077https://eccc.weizmann.ac.il/report/2007/077Comments and Revisions published for TR07-077en-usFri, 10 Aug 2007 18:27:38 +0300
Paper TR07-077
| Testing for Concise Representations |
Ilias Diakonikolas,
Homin Lee,
Kevin Matulef,
Krzysztof Onak,
Ronitt Rubinfeld,
Rocco Servedio,
Andrew Wan
https://eccc.weizmann.ac.il/report/2007/077We 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 et al. to work for non-Boolean functions, and give 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 Omega-tilde(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.
Fri, 10 Aug 2007 18:27:38 +0300https://eccc.weizmann.ac.il/report/2007/077