Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-080 | 20th May 2016 14:21

Reducing testing affine spaces to testing linearity

Revision #1
Authors: Oded Goldreich
Accepted on: 20th May 2016 14:21
Keywords:

Abstract:

We consider the task of testing whether a Boolean function $f:\{0,1\}^\ell\to\{0,1\}$
is the indicator function of an $(\ell-k)$-dimensional affine space.
An optimal tester for this property was presented by Parnas, Ron, and Samorodnitsky ({\em SIDMA}, 2002), by mimicking the celebrated linearity tester (of Blum, Luby and Rubinfeld, {\em 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:\{0,1\}^\ell\to\{0,1\}^k$, yielding an almost optimal tester.

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.

Changes to previous version:

We resolve a problem left open in our previous posting, of a couple of days ago. This new material, which refers to the problem of testing monomials, appears in Section~5.
The prior text was adapted quite superficially.

Paper:

TR16-080 | 18th May 2016 18:05

Reducing testing affine spaces to testing linearity

TR16-080
Authors: Oded Goldreich
Publication: 18th May 2016 18:05
We consider the task of testing whether a Boolean function $f:\{0,1\}^\ell\to\{0,1\}$
is the indicator function of an $(\ell-k)$-dimensional affine space.
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:\{0,1\}^\ell\to\{0,1\}^k$, yielding an almost optimal tester.