Guest Post: Oded Goldreich, “Reducing testing affine spaces to testing linearity”

[We are delighted to have this month a blog post by Oded Goldreich, on a reduction from testing affinity of subspaces to testing linearity of Boolean functions. Oded also gave us open problems directly related to this post.]

We consider the task of testing whether a Boolean function \(f\colon \{0,1\}^\ell\to\{0,1\}\) is the indicator function of an \((\ell-k)\)-dimensional 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 this task can be reduced to testing the linearity of a related function \(g\colon\{0,1\}^\ell\to\{0,1\}^k\), yielding an almost optimal tester.

Introduction

Revising our lecture notes on property testing towards a forthcoming book, we were baffled by the tester of (monotone) monomial suggested by Parnas, Ron, and Samorodnitsky [PRS]. This tester generalizes their tester of dictatorship, and does so by following the same strategy and using similar arguments at each step.

Specifically, the basic strategy consists of two steps. First, one tests whether the input function \(f\colon \{0,1\}^\ell\to\{0,1\}\) defines an \((\ell-k)\)-dimensional affine space, where the space defined by \(f\) is \(f^{-1}(1)\). In the case of dictatorship (i.e., \(k=1\)), this amounts to testing whether \(f\) is an affine function, but in the case of \(k>1\) a new task arises. In the second step, one tests whether this affine space is of the right form (i.e., a translation by \(1^\ell\) of a linear space spanned by axis-parallel vectors). In the case of \(k=1\) this amounts to testing whether the linear function is 1-linear, but in the case of \(k \geq 1\) another new task arises.

Both the aforementioned tasks are solved by by Parnas, Ron, and Samorodnitsky [PRS], but the solutions mimic the solutions used in the case of \(k=1\). Furthermore, in both cases, the generalization is very cumbersome. We find this state of affairs quite annoying, and believe that one should be able to reduce the general case to the special case. We managed to do so for the first task (i.e., testing affine spaces), and present this reduction here. We are not aware of other approaches to these tasks, and would be grateful for any information regarding this matter.

Warning: The rest of the text is tentatively adapted from my lecture notes. In particular, two of the sections (first and second reductions) reproduce the text of two exercises and their solution guidelines. If it will turn out that this contents was not know, then I may revise the text.

Perspective: Testing monomials

The ideas that underlie the tests of (monotone) dictatorship can be extended towards testing the set of functions that are (monotone) \(k\)-monomials, for any \(k\geq1\).

Definition. (monomial and monotone monomial): A function \(f\colon \{0,1\}^\ell\to\{0,1\}\) is called a \(k\)-monomial if for some \(k\)-subset \(I\subseteq[\ell]\) and \(\sigma=\sigma_1\cdots\sigma_\ell\in\{0,1\}^\ell\) it holds \(f(x)=\wedge_{i\in I}(x_i\oplus\sigma_i)\). It is called a monotone \(k\)-monomial if \(\sigma=0^\ell\).

Indeed, the definitions of (regular and monotone) dictatorship coincide with the notions of (regular and monotone) \(1\)-monomials. We focus on the task of testing monotone \(k\)-monomials, while recalling that the task of testing \(k\)-monomials is reducible to it (see [PRS] or our lecture notes). We also recall that the problem is of interest only when the proximity parameter, denoted \(\epsilon\), is small (in relation to \(2^{-k}\)). In contrast, when \(\epsilon>2^{-k+2}\), we may just estimate the density of \(f^{-1}(1)\) and accept if and only if the estimate is below \(2^{-k+1}\).

We start by interpreting the dictatorship tester in a way that facilitates its generalization. If \(f\) is a monotone dictatorship, then \(f^{-1}(1)\) is an \((\ell-1)\)-dimensional affine subspace (of the \(\ell\)-dimensional space \(\{0,1\}^\ell\)). Specifically, if \(f(x)=x_i\), then this subspace is \(\{x\in\{0,1\}^\ell \colon x_i=1\}\). In this case, the linearity tester could be thought of as testing that \(f^{-1}(1)\) is an arbitrary \((\ell-1)\)-dimensional subspace, whereas the “conjunction test” verifies that this subspace is an affine translation by \(1^\ell\) of a linear space that is spanned by \(\ell-1\) unit vectors (i.e., vectors of Hamming weight 1).1

Now, if \(f\) is a monotone \(k\)-monomial, then \(f^{-1}(1)\) is an \((\ell-k)\)-dimensional affine subspace. So the idea is to first test that \(f^{-1}(1)\) is an \((\ell-k)\)-dimensional affine subspace, and then to test that it is an affine subspace of the right form (i.e., it has the form \(\{x\in\{0,1\}^\ell:(\forall i\in I)\;x_i\!=\!1\}\), for some \(k\)-subset \(I\)). Following are outlines of the treatment of these two tasks in [PRS].

Testing affine subspaces

Suppose that the alleged affine subspace \(H\) is presented by a Boolean function \(h\) such that \(h(x)=1\) if and only if \(x\in H\). (Indeed, in our application, \(h=f\).) We wish to test that \(H\) is indeed an affine subspace.

(Actually, we are interested in testing that \(H\) has a given dimension, but this extra condition can be checked easily by estimating the density of \(H\) in \(\{0,1\}^\ell\), since we are willing to have complexity that is inversely proportional to the designated density (i.e., \(2^{-k}\)).)2

This task is related to linearity testing and it was indeed solved in [PRS] using a tester and an analysis that resembles the standard linearity tester of [BLR]. Specifically, the tester selects uniformly \(x,y\in H\) and \(z\in\{0,1\}^\ell\) and checks that \(h(x+y+z)=h(z)\) (i.e., that \(x+y+z\in H\) if and only if \(z\in H\)). Indeed, we uniformly sample \(H\) by repeatedly sampling \(\{0,1\}^\ell\) and checking whether the sampled element is in \(H\).

Note that, for co-dimension \(k>1\), the function \(h\) is not affine; that is, \(x,y\not\in H\) does not imply \(x+y\not\in H\). Still, testing affine subspaces can be reduced to testing linearity, providing an alternative to the presentation of [PRS], and doing so is the core of this note (see next section).

Testing that an affine subspace is a translation by \(1^\ell\) of a linear subspace spanned by unit vectors

Suppose that an affine subspace \(H’\) is presented by a Boolean function, denoted \(h’\), and that we wish to test that \(H’\) has the form \(\left\{1^\ell+\sum_{i\in[\ell]\setminus{I}}c_ie_i: c_1,…,c_\ell\in\{0,1\}\right\}\), where \(e_1,…,e_\ell\in\{0,1\}^\ell\) are unit vectors, and \(I\subseteq[\ell]\) is arbitrary. That is, we wish to test that \(h'(x)=\wedge_{i\in I}x_i\).

This can be done by picking uniformly \(x\in H’\) and \(y\in\{0,1\}^\ell\), and checking that \(h'(x\wedge y)=h'(y)\) (i.e., \(x\wedge y\in H’\) if and only if \(y\in H’\)). Note that if \(H’\) has the form \(1^\ell+L\), where \(L\) is a linear subspace spanned by the unit vectors \(\{e_i:i\in[\ell]\setminus I\}\) for some \(I\), then \(h'(z)=\wedge_{i\in I}z_i\) holds for all \(z\in\{0,1\}^\ell\) and \(h'(x\wedge y)=h'(x)\wedge h'(y)\) holds for all \(x,y\in\{0,1\}^\ell\). On the other hand, as shown in [PRS], if \(H’\) is an affine subspace that does not have the foregoing form, then the test fails with probability at least \(2^{-k-1}\).

However, as in the case of \(k=1\), we do not have access to \(h’\) but rather to a Boolean function \(h\) that is (very) close to \(h’\). So we need to obtain the value of \(h’\) at specific points by querying \(h\) at uniformly distributed points. Specifically, the value of \(h’\) at \(z\) is obtained by uniformly selecting \(r,s\in h^{-1}(1)\) and using the value \(h(r+s+z)\). In other words, we self-correct \(h\) at any desired point by using the value of \(h\) at random elements of \(h^{-1}(1)\), while actually hoping that these points reside in the affine subspace \(H’\). This hope is likely to materialize when \(h\) is \(0.01\cdot2^{-k}\)-close to \(h’\).

The foregoing is indeed related to the conjunction check performed as part of the dictatorship tester of [BGS,PRS], and the test and the analysis in [PRS] (for the case of \(k>1\)) resemble the corresponding parts in [BGS,PRS] (which handle the case of \(k=1\)). We would welcome a simple and clean reduction from the general case (of any \(k\geq1\)) to the special case (of \(k=1\)).

The reduction

We start by restating the problem. We are given access to a Boolean function \(h\colon \{0,1\}^\ell\to\{0,1\}\) and wish to testing whether \(h^{-1}(1)\) is an \((\ell-k)\)-dimensional affine subspace by reducing this problem to testing linearity. We present two reductions. The first (and simpler) reduction increasing the complexities by a factor of \(2^k\), whereas the second reduction only incurs an overhead of \(\tilde{O}(\log(1/\epsilon))\).

The first reduction

Define a function \(g\colon \{0,1\}^\ell\to\{0,1\}^k\cup\{\bot\}\) such that if \(H\stackrel{\rm def}{=} h^{-1}(1)\) is affine then \(g\) (ranges over \(\{0,1\}^k\) and) is affine and \(g^{-1}(0^k)=H\). The definition of \(g\) is based on any fixed sequence of linearly independent vectors \(v^{(1)},…,v^{(k)}\in\{0,1\}^\ell\) such that for some \(u\in H\) and every non-empty \(I\subseteq[k]\) it holds that \(u+\sum_{i\in I}v^{(i)}\not\in H\). (If \(H\) is an \((\ell-k)\)-dimensional affine space, then these \(v^{(i)}\)’s form a basis for a \(k\)-dimensional space that intersects \(H-u\) only at \(0^\ell\).) Fixing such a sequence, define \(g\colon \{0,1\}^\ell\to\{0,1\}^k\cup\{\bot\}\) such that \(g(x)=(c_1,…,c_k)\) if \((c_1,…,c_k)\in\{0,1\}^k\) is the unique sequence that satisfies \(x+\sum_{i\in[k]}c_iv^{(i)}\in H\) and let \(g(x)=\bot\) otherwise. (Whenever we say that \(g\) is affine, we mean, in particular, that it never assumes the value \(\bot\).)3 The outline of the proof and the reduction are as follows.

  • Show that \(H\) is an \((\ell-k)\)-dimensional affine space if and only if \(g\) (as defined above) is a surjective affine function.
  • Show that if \(H\) is an \((\ell-k)\)-dimensional affine space, then a sequence as underlying the definition of \(g\) can be found (w.h.p.) by making \(O(2^k)\) queries to \(h\).
  • Reduce testing whether \(g\) is affine to testing whether the mapping \(x\mapsto g(x)-g(0^\ell)\) is linear.
  • Assuming that \(g\) is affine, show that testing whether it is surjective can be done by making \(O(2^k)\) queries to \(h\). (It is indeed easier to perform such a check by using \(O(2^k)\) queries to \(g\).)

Combining the above ideas, the claimed reduction will follow (as farther detailed below). Note that this reduction has two-sided error, and that the resulting tester has query complexity \(O(2^k/\epsilon)\) (rather than \(O(1/\epsilon)\), all in case \(\epsilon < 2^{-k+2}\)).4

Let \(V\) be a \(k\)-by-\(\ell\) full rank matrix such that for some \(u\in H\) it holds that \(u+cV\in H\) implies \(c=0^k\) (i.e., the rows of \(V\) are the \(v^{(i)}\)’s of the hypothesis). Recall that \(g\colon \{0,1\}^\ell\to\{0,1\}^k\) is defined such that \(g(x)=c\) if \(c\in\{0,1\}^k\) is the unique vector that satisfies \(x+cV\in H\) (and \(g(x)=\bot\) if the number of such vectors is not one). Note that \(g^{-1}(0^k)\subseteq H\) always holds (since \(g(x)=c\) implies \(x+cV\in H\)), and that when \(g\) never assumes the value \(\bot\) equality holds (since in this case \(x+cV\in H\) implies that \(g(x)=c\)).

Now, on the one hand, if \(H\) is an \((\ell-k)\)-dimensional affine space, then, for some full-rank \((\ell-k)\)-by-\(\ell\) matrix \(G\), it holds that \(H=\{yG+u:y\in\{0,1\}^{\ell-k}\}\). In this case, \(g\) is a surjective affine function (since for every \(x\) there exists a unique representation of \(x-u\) as \(yG+cV\), which implies \(x-u+cV = yG \in H-u\), and so \(g(x)=c\)).5

On the other hand, if \(g\) is a surjective affine function (i.e., \(g(x)=xT+s\) for some full-rank \(\ell\)-by-\(k\) matrix \(T\) and \(s\in\{0,1\}^k\)), then \(H=\{x:g(x)=0^k\}\), which implies that \(H\) is an \((\ell-k)\)-dimensional affine subspace. It follows that if \(g\) is \(\epsilon\)-close to being a surjective affine function,
then \(g^{-1}(0^k)\) is \(\epsilon\)-close to being an (\((\ell-k)\)-dimensional) affine space (i.e., the indicator functions of these sets are \(\epsilon\)-close). In light of the above, consider the following algorithm.

  1.  Using \(O(2^k)\) queries to \(h\), try to find \(u\in H\) and a \(k\)-by-\(\ell\) matrix \(V\) such that for any non-zero \(c\in\{0,1\}^k\) it holds that \(u+cV\not\in H\). (A vector in \(H\) can be found by making \(O(2^k)\) random trials, and once it is found the matrix \(V\) can be found in \(k\) iterations such that in the \(i\)-th iteration we try to find a vector \(v^{(i)}\) such that \(u+\sum_j c_jv^{(j)}\not\in H\) holds for every \((c_1,…,c_i)\in\{0,1\}^i\setminus\{0^i\}\).)
    If such a matrix \(V\) is found, then proceed to the next step. Otherwise, reject.
  2. Test whether the function \(g\colon \{0,1\}^\ell\to\{0,1\}^k\) (defined based on this \(V\)) is affine, and reject if the affinity tester rejects. When the tester queries \(g\) at \(x\), query \(h\) on \(x+cV\) for all \(c\in\{0,1\}^k\), and answer accordingly; that is, the answer is \(c\) if \(c\) is the unique vector satisfying \(h(x+cV)=1\), otherwise (i.e., \(g(x)=\bot\)) the execution is suspended and the algorithm rejects.
  3. Test whether \(g\) is surjective. Assuming that \(g\) is affine, the task can be performed as follows.
    1. Select uniformly at random a target image \(c\in\{0,1\}^k\).
    2. Select uniformly at random a sample \(S\) of \(t=O(2^k)\) elements in \(\{0,1\}^\ell\), and accept if and only if there exists \(x\in S\) such that \(x+cV\in H\) (i.e., \(g(x)=c\)).
      We stress that we do not compute \(g\) at \(x\), which would have required \(2^k\) queries to \(h\), but rather check whether \(g(x)=c\) by making a single query to \(h\) (i.e., we query \(h\) at \(x+cV\)). (Recall that if \(g\) is affine and surjective, then each \(c\in\{0,1\}^k\) has \(2^{\ell-k}\) preimages under \(g\).)

    Recall that if \(g\) is affine but not surjective, then its image has size at most \(2^{k-1}\).

Recall that testing whether \(g\colon \{0,1\}^\ell\to\{0,1\}^k\) is affine reduces to testing whether \(f(x)\stackrel{\rm def}{=} g(x)-g(0)\) is a homomorphism (see the last paragraph in the lecture on linearity testing).

Note. An alternative presentation may start by reducing testing whether \(H\) is an \((\ell-k)\)-dimensional affine space to testing whether \(H-u\) is an \((\ell-k)\)-dimensional linear space, where \(u\in H\).

The second reduction

Let \(h\colon \{0,1\}^\ell\to\{0,1\}\) be a Boolean function. In the previous section, we reduced \(\epsilon\)-testing whether \(h^{-1}(1)\) is an \((\ell-k)\)-dimensional affine subspace to \(\epsilon\)-testing the affinity of a function \(g\), where the value of \(g\) at any point can be computed by making \(2^k\) queries to \(h\). (Indeed, that reduction made \(O(2^k)\) additional queries to \(h\).) This yields an \(\epsilon\)-tester of time complexity \(O(2^k/\epsilon)\) for testing affine subspaces. Recall that, for every \(\epsilon_0<1/4\), if \(g\) is \(\epsilon_0\)-close to being an affine function, then it is \(\epsilon_0\)-close to a unique affine function \(g’\), which can be computed by self-correction of \(g\) (where each invocation of the self-corrector makes two queries to \(g\) and is correct with probability at least \(1-2\epsilon_0\)). This suggests the following algorithm.

  1. Test that \(g\) is \(0.2\)-close to a surjective affine function. This step can be implemented in time \(O(2^k)\), by using the tester of the previous section. Let \(g’\) denote the affine function closest to \(g\).
  2. Test that \(h\) is \(\epsilon\)-close to \(h’colon\{0,1\}^\ell\to\{0,1\}\), where \(h'(x)=1\) if and only if \(g'(x)=0^k\). We implement this step in complexity \(\tilde{O}(1/\epsilon)\) by taking a sample of \(m=O(1/\epsilon)\) pairwise independent points in \(\{0,1\}^\ell\) such that evaluating \(g’\) on these \(m\) points only requires time \(O(m+2^k\cdot\tilde{O}(\log m))\). Specifically, for \(t=\lceil{\log_2(m+1)\rceil}\), select uniformly \(s^{(1)},\dots,s^{(t)}\in\{0,1\}^\ell\), compute each \(g'(s^{(j)})\) via self-correcting \(g\), with error probability \(0.01/t\), and use the sample points \(r^{(J)}=\sum_{j\in J}s^{(j)}\) for all non-empty subsets \(\subseteq[t]\).

Show that the above algorithm constitutes an \(\epsilon\)-tester of time complexity \(O(\epsilon^{-1}+2^k\cdot\tilde{O}(\log(1/\epsilon)))\) for \((\ell-k)\)-dimensional affine subspaces. The key observation here is that \(g'(\sum_{j\in J}s^{(j)})= \sum_{j\in J}g'(s^{(j)})\), and that the \(r^{(J)}\)’s are pairwise independent.6



[1] That is, we requires that this subspace has the form \(\left\{1^\ell+\sum_{j\in([\ell]\setminus\{i\})}c_je_j : c_1,\dots,c_\ell\in\{0,1\}\right\}\), where \(e_1,…,e_\ell\in\{0,1\}^\ell\) are the \(\ell\) unit vectors (i.e., vectors of Hamming weight 1).
[2] Recall that if \(\epsilon \leq 2^{-k+2}\), then \(O(2^k)=O(1/\epsilon)\), and otherwise (i.e., for \(\epsilon\geq 2^{-k+2}\)) we can proceed by estimating the density of \(h^{-1}(1)\).
[3] Indeed, when emulating \(g\) for the affinity tester, we shall reject if we ever encounter the value \(\bot\).
[4] Needless to say, we would welcome a one-sided error reduction. Recall that the case \(\epsilon\geq 2^{-k+2}\) can be handled by density estimation. A complexity improvement for the main case (of \(\epsilon < 2^{-k+2}\)) appears in the next section.
[5] This uses the fact that \(V\) is a basis for a \(k\)-dimensional linear space that intersects the \((\ell-k)\)-dimensional linear space \(H-u\) only in \(0^\ell\).
[6] This is inspired by [GL] (as presented in [Gol, Sec. 7.1.3]).


References

[BGS] M. Bellare, O. Goldreich and M. Sudan. Free Bits, PCPs and Non-Approximability — Towards Tight Results. SIAM Journal on Computing, Vol. 27, No. 3, pages 804–915, 1998. Extended abstract in 36th FOCS, 1995.
[BLR] M. Blum, M. Luby and R. Rubinfeld. Self-Testing/Correcting with Applications to Numerical Problems. Journal of Computer and System Science, Vol. 47, No. 3, pages 549–595, 1993. Extended abstract in 22nd STOC, 1990.
[Gol] O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
[GL] O. Goldreich and L.A. Levin. A hard-core predicate for all one-way functions. In the proceedings of 21st ACM Symposium on the Theory of Computing, pages 25–32, 1989.
[PRS] 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.

One thought on “Guest Post: Oded Goldreich, “Reducing testing affine spaces to testing linearity”

  1. Oded Goldreich

    I have just posted a revised version of this text on ECCC (see TR16-080).
    The new presentation is more detailed and eliminates a few gaps in the present version.

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload the CAPTCHA.