__
Revision #1 to TR22-104 | 4th October 2022 10:57
__
#### On One-Sided Testing Affine Subspaces

**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.

**Changes to previous version:**
A new description of the main tester

__
TR22-104 | 18th July 2022 12:02
__

#### On One-Sided Testing Affine Subspaces

**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.