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. 16 with ideas from learning theory, and yields property testers that make po! y(s/epsiv) queries (independent of n) for Boolean function classes such as s-term DNF formulas (answering a question posed by Parnas et al. [12]), sizes. decision trees, sizes Boolean formulas, and sizes 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 van at ion/row 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/e)-query testing algorithms for non-Boolean valued function classes such as sizes algebraic circuits and s-sparse polynomials over finite fields. We also prove an Omega(radic(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.

Authors

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

Keywords

• Circuit testing
• Polynomials
• Decision trees
• Galois fields
• Boolean functions
• Computer science
• Input variables
• Neural networks
• Binary decision diagrams
• Representational Content
• Decision Tree
• Functional Class
• Testing Algorithm
• Finite Field
• Boolean Function
• Lower Bound
• Uniform Distribution
• Learning Algorithms
• Running Time
• Random Walk
• Finite Set
• Generation Algorithm
• Types Of Representations
• Linear Form
• Monomial
• Fourier Coefficients
• Implicit Learning
• Statistical Distance
• Affine Function
• Proper Learning
• Subset Of Indices
• Standard Argument
• Black-box Function
• Concept Of Class
• High Probability