Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #4 to TR16-080 | 14th March 2020 20:18

#### Reducing testing affine spaces to testing linearity

Revision #4
Authors: Oded Goldreich
Accepted on: 14th March 2020 20:18
Downloads: 37
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.

Changes to previous version:

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.

Revision #3 to TR16-080 | 22nd October 2019 21:58

#### Reducing testing affine spaces to testing linearity

Revision #3
Authors: Oded Goldreich
Accepted on: 22nd October 2019 21:58
Downloads: 96
Keywords:

Abstract:

For any finite field $F$ and $k<\ell$, we consider the task of testing whether a function $f:F^\ell\to\{0,1\}$ is the indicator function of an $(\ell-k)$-dimensional affine space. An optimal tester for this property (for the case of $F=GF(2)$)
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 efficiently reduced to testing the linearity of a related function $g:F^\ell\to F^k$. This reduction yields an almost optimal tester for affine spaces (represented by their indicator function).

Recalling that Parnas, Ron, and Samorodnitsky used testing $(\ell-k)$-dimensional affine spaces as the first step in a two-step procedure for testing $k$-monomials, we also show that the second step in their procedure can be reduced to the special case of $k=1$.

Changes to previous version:

correcting some typos.
updating the abstract in the record.

Revision #2 to TR16-080 | 22nd October 2019 01:48

#### Reducing testing affine spaces to testing linearity

Revision #2
Authors: Oded Goldreich
Accepted on: 22nd October 2019 01:48
Downloads: 98
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.

Changes to previous version:

The reduction of testing affine spaces to testing linearity (of functions) is extended to arbitrary finite fields,
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
(i.e., the original Sections 3 and 5 have been merged
and placed after the original Section 4.)

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
Downloads: 524
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
Downloads: 706
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.

ISSN 1433-8092 | Imprint