Testing for Concise Representations
Testing for Concise Representations
复制标题
测试简洁表示
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Andrew Wan
中科院分区：
文献类型：
--
作者：
Ilias Diakonikolas;Homin K. Lee;Kevin Matulef;Krzysztof Onak;R. Rubinfeld;R. Servedio;Andrew Wan
我们描述了一个通用的方法来测试是否有一个函数的n个输入变量有一个简洁的表示。该方法结合了Fischer等人16的军政府测试的思想和学习理论的思想，并产生了使PO！y（s/epsiv）查询（与n无关）布尔函数类，例如s项DNF公式（回答Parnas等人提出的问题。[12]）、大小。决策树、大小布尔公式和大小布尔电路。该方法也可以应用于非布尔值函数类。这是通过将离子/行Fischer等人的货车概念推广到非布尔函数来实现的。使用这种推广，我们扩展了原来的junta测试Fischer等人。工作的非布尔函数，并给出多（S/E）查询测试算法的非布尔值函数类，如大小代数电路和s-稀疏多项式在有限域。我们还证明了一个欧米茄（radic（s））查询下界的非自适应测试s-稀疏多项式在有限域的恒定大小。这表明，在某些情况下，我们的一般方法产生一个属性测试与查询复杂性是最佳的（非自适应算法）多项式因子。
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.