We show that every non-adaptive property testing algorithm making a constant number of queries, over a fixed alphabet, can be converted to a sample-based (as per [Goldreich and Ron, 2015]) testing algorithm whose average number of queries is a fixed, smaller than $1$, power of $n$. Since the query distribution of the sample-based algorithm is not dependent at all on the property, or the original algorithm, this has many implications in scenarios where there are many properties that need to be tested for concurrently, such as testing (relatively large) unions of properties, or converting a Merlin-Arthur Proximity proof (as per [Gur and Rothblum, 2013]) to a proper testing algorithm.ududThe proof method involves preparing the original testing algorithm for a combinatorial analysis. For the analysis we develop a structural lemma for hypergraphs that may be of independent interest. When analyzing a hypergraph that was extracted from a $2$-sided test, it allows for finding generalized sunflowers that provide for a large-deviation type analysis. For $1$-sided tests the bounds can be improved further by applying Janson's inequality directly over our structures.
展开▼
机译：我们表明，每一个在固定字母上进行恒定数量查询的非自适应属性测试算法都可以转换为基于样本的测试算法（根据[Goldreich and Ron，2015]），其平均查询数量为固定的，小于$ 1 $，幂为$ n $。由于基于样本的算法的查询分布完全不依赖于属性或原始算法，因此，在需要同时测试许多属性（例如测试（相对较大））的场景中，这具有许多含义。属性并集，或将Merlin-Arthur邻近证明（根据[Gur and Rothblum，2013]）转换为适当的测试算法。 ud ud证明方法包括准备用于组合分析的原始测试算法。为了进行分析，我们为超图开发了一个结构引理，该引理可能具有独立的意义。分析从$ 2 $边测试中提取的超图时，它可以查找提供大偏差类型分析的广义向日葵。对于$ 1 $边测试，可以通过直接在我们的结构上应用Janson的不等式来进一步改善界限。
展开▼
