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").

Material available on-line


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