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.

A new description of the main tester

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.