ECCC-Report TR16-080https://eccc.weizmann.ac.il/report/2016/080Comments and Revisions published for TR16-080en-usSat, 14 Mar 2020 20:18:29 +0200
Revision 4
| Reducing testing affine spaces to testing linearity |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/080#revision4We 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.
Sat, 14 Mar 2020 20:18:29 +0200https://eccc.weizmann.ac.il/report/2016/080#revision4
Revision 3
| Reducing testing affine spaces to testing linearity |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/080#revision3For 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$.
Tue, 22 Oct 2019 21:58:10 +0300https://eccc.weizmann.ac.il/report/2016/080#revision3
Revision 2
| Reducing testing affine spaces to testing linearity |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/080#revision2We 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.
Tue, 22 Oct 2019 01:48:43 +0300https://eccc.weizmann.ac.il/report/2016/080#revision2
Revision 1
| Reducing testing affine spaces to testing linearity |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/080#revision1We 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.
Fri, 20 May 2016 14:21:38 +0300https://eccc.weizmann.ac.il/report/2016/080#revision1
Paper TR16-080
| Reducing testing affine spaces to testing linearity |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2016/080We 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.
Wed, 18 May 2016 18:05:36 +0300https://eccc.weizmann.ac.il/report/2016/080