Paper detail

An Optimal Tester for $k$-Linear

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.