论文标题
$ k $ -linear的最佳测试仪
An Optimal Tester for $k$-Linear
论文作者
论文摘要
布尔函数$ f：\ {0,1 \}^n \ to \ {0,1 \} $是$ k $ -linear如果返回输入的$ k $ coordinates的总和（二进制字段$ f_2 $）。在本文中，我们研究了$ k $ -linear的类的属性测试，所有$ k $ - 线性功能的类和$ k $ -linear $^*$，类$ \ cup_ {j = 0}^kj $ -linear。我们为$ k $ linear提供了非自适应分配的$ε$ -TESTER，该$ k $ -linear使$$ o \ left（k \ log k+k+\ frac {1}ε\ right）$$查询。这匹配了文献中已知的下限。 然后，我们给出一个非自适应分配的$ε$ -TESTER，用于$ k $ -linear $^*$，它具有相同数量的查询，并表明任何非自适应均匀分发的单层$ε$ -TESTER $ k $ -linear for $ k $ -linear for $ k $ -linear for $ k $ -linear必须至少使$ \ tilde $ \ tildepireme（k）\ log n+n+ω（1/^）（1/^）。后者的界限几乎与文献中已知的上限$ o（k \ log n+1/ε）$匹配。然后，我们证明任何自适应统一分布的单面$ε$ -TESTER $ k $ - 线性必须至少使$ \tildeΩ（\ sqrt {k}）\ log n+n+ω（1/ε）$查询。
A Boolean function $f:\{0,1\}^n\to \{0,1\}$ is $k$-linear if it returns the sum (over the binary field $F_2$) of $k$ coordinates of the input. In this paper, we study property testing of the classes $k$-Linear, the class of all $k$-linear functions, and $k$-Linear$^*$, the class $\cup_{j=0}^kj$-Linear. We give a non-adaptive distribution-free two-sided $ε$-tester for $k$-Linear that makes $$O\left(k\log k+\frac{1}ε\right)$$ queries. This matches the lower bound known from the literature. We then give a non-adaptive distribution-free one-sided $ε$-tester for $k$-Linear$^*$ that makes the same number of queries and show that any non-adaptive uniform-distribution one-sided $ε$-tester for $k$-Linear must make at least $ \tildeΩ(k)\log n+Ω(1/ε)$ queries. The latter bound, almost matches the upper bound $O(k\log n+1/ε)$ known from the literature. We then show that any adaptive uniform-distribution one-sided $ε$-tester for $k$-Linear must make at least $\tildeΩ(\sqrt{k})\log n+Ω(1/ε)$ queries.
