This work presents a one-sided error tester for affine subspaces that is simpler than the one presented in reference [16].
My own view of the tester is different from the one offered in Section 2.1 of the paper. In particular, the reduction of the affine case to the linear case (attributed to [16]) is the most obvious aspect of [16], and the core of both papers is the linear case. In both papers, testing linear subspaces is done by an iterative process that gradually increases a lower bound on the co-dimension of the tested subspace, where each increase is backed by reliable evidence. The iterative processes in the two papers are fundamentally different, since they are pivoted at different characterizations of linear subspaces. Consequently, the iterative process in the current paper is more clear than the one in [16, Sec 4.1], and avoids the need for an efficiency improvement as in [16, Sec 4.2].
The pivot of the current paper is a notion called `well-structured' subspace, which is better called systematic by analogy to coding theory. A $(n-d)$-dim subspace is so called if the first $n-d$ coordinates in it are free (i.e., can assume any value), whereas the remaining $d$ coordinates are a linear function of the first $n-d$ coordinates. It is quite easy to test this property; this is done in three sub-steps.
The main step is an iterative process that tries to construct a linear mapping $M$ of the tested subspace to a well-structured one. In each iteration the process either rejects (with an evidence that the subspace is not linear) or increase the co-dimension of the well-structured space. The process is rooted in the observation that if $f$ describes an $d^*$-dim linear subspace, then for every $d\leq d^*$, there exists a non-singular matrix $M$ such that the $n-d$-prefix of the function $f_d(x) = f(xM)$ is free. Furthermore, given a matrix for $f_d$, if $d$ is smaller than $d^*$, then one can obtain a corresponding $M'$ for $f_{d+1}$ by finding an $(n-d)$-long prefix that has no suitable suffix.
(The complexity improvement (of a factor of $|F|$) over [16] is due to the fact that each iteration in the current paper has complexity related to $\tildeO(1/\epsilon)$, where the complexity of the $i^\xth$ iteration in [16] has an added term of $|F|^{i+1}$ whereas $i \leq \log_{|F|}(2/\epsilon)$.)
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.
Available from ECCC TR22-104.