ECCC-Report TR20-123https://eccc.weizmann.ac.il/report/2020/123Comments and Revisions published for TR20-123en-usMon, 17 Aug 2020 16:17:37 +0300
Paper TR20-123
| An Optimal Tester for k-Linear |
Nader Bshouty
https://eccc.weizmann.ac.il/report/2020/123A 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 $\epsilon$-tester for $k$-Linear that makes
$$O\left(k\log k+\frac{1}{\epsilon}\right)$$ queries.
This matches the lower bound known from the literature.
We then give a non-adaptive distribution-free one-sided $\epsilon$-tester for $k$-Linear$^*$ that makes the same number of queries and show that any non-adaptive uniform-distribution one-sided $\epsilon$-tester for $k$-Linear must make at least $ \tilde\Omega(k)\log n+\Omega(1/\epsilon)$ queries. The latter bound, almost matches the upper bound $O(k\log n+1/\epsilon)$ known from the literature. We then show that any adaptive uniform-distribution one-sided $\epsilon$-tester for $k$-Linear must make at least $\tilde\Omega(\sqrt{k})\log n+\Omega(1/\epsilon)$ queries.Mon, 17 Aug 2020 16:17:37 +0300https://eccc.weizmann.ac.il/report/2020/123