Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR22-104 | 18th July 2022 12:02

#### On One-Sided Testing Affine Subspaces

TR22-104
Publication: 18th July 2022 15:43
Keywords:

Abstract:

We study the query complexity of one-sided $\epsilon$-testing the class of Boolean functions $f:F^n\to \{0,1\}$ that describe affine subspaces and Boolean functions that describe axis-parallel affine subspaces, where $F$ is any finite field. We give a polynomial-time $\epsilon$-testers that ask $\tilde O(1/\epsilon)$ queries. This improves the query complexity $\tilde O(|F|/\epsilon)$ in~[16].

We then show that any one-sided $\epsilon$-tester with proximity parameter $\epsilon<1/|F|^d$ for the class of Boolean functions that describe $(n-d)$-dimensional affine subspaces and Boolean functions that describe axis-parallel $(n-d)$-dimensional affine subspaces must make at least
$\Omega(1/\epsilon+|F|^{d-1}\log n)$ and $\Omega(1/\epsilon+|F|^{d-1}n)$ queries, respectively.
This improves the lower bound $\Omega(\log n/\log\log n)$ that is proved in~[16] for $F=GF(2)$. We also give testers for those classes with query complexity that almost match the lower bounds.

ISSN 1433-8092 | Imprint