Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-123 | 17th August 2020 10:18

#### An Optimal Tester for k-Linear

TR20-123
Publication: 17th August 2020 16:17
Keywords:

Abstract:

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 $\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.

ISSN 1433-8092 | Imprint