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

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

[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.