# Open problem for April 2016

As open problems of the month, we state here the two questions discussed in our recent guest post by Oded Goldreich:

Open Problem 1 (obtaining a one-sided error reduction): The reduction from testing affinity of a subspace to that of testing affinity of a function has two-sided error probability. We wonder whether a one-sided error reduction of similar complexity can be found.

Note that this will yield a one-sided error tester for affinity, which we believe is not known. Actually, we would also welcome a two-sided error reduction that, when combined with the linearity tester, yields a tester of complexity $$O(1/\epsilon)$$ rather than $$\tilde{O}(1/\epsilon)$$.

Turning to the task of testing monomials, we recall that the solution of [PRS02] is based on employing self-correction to the following test that refers to the case that $$H=\{x:AX=b\}$$ is an $$(\ell-k)$$-dimensional affine space. Basically, the test selects a random $$x\in H$$ and a random $$y\in\{0,1\}^\ell$$, and checks whether it holds that $$y\in H$$ if and only if $$x\wedge y \in H$$, where $$\wedge$$ denotes the bit-by-bit product of vectors. It is painfully shown in [5] that if $$H$$ is not a translation by $$1^\ell$$ of an axis-aligned linear space, then the check fails with probability $$\Omega(2^{-k})$$. Furthermore, it is shown that for a constant fraction of the $$x$$’s (in $$H$$), the check fails on a $$\Omega(2^{-k})$$ fraction of the $$y$$’s (in $$\{0,1\}^\ell$$). This strengthening is important, since selecting $$x\in H$$ uniformly requires $$\Theta(2^k)$$ trials. Recall that proving the foregoing assertion for $$k=1$$ is quite easy (cf. [5]), which leads us to ask

Open Problem 2 (can a simpler proof be found for the case of $$k>1$$): Is there a relatively simple reduction of the foregoing claim for general $$k$$ to the special case of $$k=1$$?

[PRS02] M. Parnas, D. Ron, and A. Samorodnitsky. Testing Basic Boolean Formulae. SIAM Journal on Disc. Math. and Alg., Vol. 16 (1), pages 20–46, 2002.