## Reducing testing affine spaces to testing linearity

#### Webpage for a paper by Oded Goldreich

#### Abstract

We consider the task of testing
whether a Boolean function $f:\bitset^\ell\to\bitset$
is the indicator function of an $(\ell-k)$-dimensional affine space.
An optimal tester for this property was presented
by Parnas, Ron, and Samorodnitsky (SIDMA, 2002),
by mimicking the celebrated linearity tester
(of Blum, Luby and Rubinfeld (JCSS, 1993))
and its analysis.
We show that the former task
(i.e., testing $(\ell-k)$-dimensional affine spaces)
can be reduced to testing
the linearity of a related function $g:\bitset^\ell\to\bitset^k$,
yielding an almost optimal tester.

**Addendum (20/5/16):**
In addition, we show that testing monomials can be performed
by using the foregoing reduction and reducing part of the analysis
to the analysis of the dictatorship test.
Specifically, in the original post we only treated the question of
testing affine spaces, which is the main module in PRS's tester for
monomials. In that post, we showed that testing
whether $f:\{0,1\}^\ell\to\{0,1\}$ describes an $(\ell-k)$-dim affine space
reduces to testing whether a
related function $g:\{0,1\}^\ell\to\{0,1\}^k$ is linear.
In the this revision,
we show that testing $k$-monomials can be performed by combining a tester
for affine spaces with a test of $g$ that generalizes the other module
in the PRS tester (i.e., the "conjunction test").

**Major revision (14/3/20):**
The current version is the result of an extensive revision.
In particular, the reduction of testing affine spaces to testing linearity
(of functions) is simplified and extended to arbitrary finite fields,
the second step in the procedure for testing $k$-monomials is revised,
many of the technical justifications are elaborated,
and some crucial typos are fixed.
In addition, the title has been augmented for clarity,
the brief introduction has been expanded,
and the high level structure has been re-organized.

#### Material available on-line

Back to
either Oded Goldreich's homepage
or general list of papers.