Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TESTING AFFINE SUBSPACES:
Reports tagged with testing affine subspaces:
TR16-080 | 18th May 2016
Oded Goldreich

#### Reducing testing affine spaces to testing linearity

Revisions: 1

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

ISSN 1433-8092 | Imprint