ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > KRZYSZTOF ONAK:
All reports by Author Krzysztof Onak:

TR07-077 | 7th August 2007
Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

Testing for Concise Representations

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 ... more >>>



ISSN 1433-8092 | Imprint