linearity

Is it the case that \[ f(x) = \chi_S(x)? \]

\[ f(x)f(y)f(x\oplus y) = f(0)? \]

Analysis: \(f(0)f*f*f(0) \ge 1-2\varepsilon.\) Thus \[ \max_S |\hat{f}(S)| \ge 1-2\varepsilon. \] Which means that \(f\) is close to some character.

direct product

PROPERTY: If \(\exists f_1,\ldots, f_k\) such that \[ g(x_1,\ldots, x_k) = (f_1(x_1), \ldots, f_k(x_k)) \] then we say that \(g\) is a direct product. We want a test to distinguish between functions which are close to direct products and functions which are far from direct products.

So here’s the test. I think it was originally introduced by Dinur.

  1. Sample \(x\) uniformly.
  2. Sample a set \(A\) of coordinates by including each coordinate in \(A\) with probability \(3/4\).
  3. Sample \(y\) as follows: for \(i\in A\), just set \(y_i = x_i\). For \(i\notin A\) sample \(y_i\) uniformly.
  4. Accept iff \(g(y)_A = g(x)_A\).
Here is my attempt at analyzing this (I haven’t read the paper yet). I think if we can prove the following lemma, then it is gg:

Lemma. \(\forall i\in[k],\) \[ \Pr_{x,y}[g_i(x)=g_i(y)\mid x_i = y_i] \ge 1-100\varepsilon. \]

Proof. Let \(B_1,B_2,B_3,B_4\) be a partition of \([k]\setminus\left\{ i\right\}\). Sample \(x^{(0)}\) uniformly randomly. Sample \(x^{(1)}\) by starting with \(x^{(0)}\) and then resampling the coordinates from \(B_1\). Sample \(x^{(2)}\) by starting from \(x^{(1)}\) and then resampling the coordinates from \(B_2\). Similar for \(x^{(3)}, x^{(4)}\).

Yay coupling.

Ok so here’s the story.

These \(x^{(i)}\)’s are all marginally uniform random points. Hence, by union bound there is at most \(8\varepsilon\) chance that any of them are bad. Assuming they are all good, my coupling thing makes it so that if we compare adjacent ones, i.e., \(x^{(i)}\) and \(x^{(i+1)}\) then they are very likely to agree.

But at the end of the process we have \(x^{(0)}\) and \(x^{(4)}\) being completely unrelated things, except that they agree in bit \(i\). But by this chain of reasoning we see that \(g_i(x^{(0)})\) and \(g_i(x^{(4)})\) are actually quite likely to agree. In otherwords, we have shown that \(g\) is pretty consistent in the value of \(g_i(x)\) when \(x_i\) is held constant. So there is a natural way to define the direct product and it should work.

ok so, upon further contemplation this lemma is not really what we wanted. Like this only gives that we are distance \(d\varepsilon\) from linear I think. But Dinur claims \(O(\varepsilon)\). So maybe you need something fancier for that.

direct sum: Shapka test

There are more efficient tests for direct sum: this one uses a large number of queries. But it’s quite simple to analyze, so that’s nice. It’s by Dinur et at.

I don’t quite parse what they have written. But here’s something that makes sense.

Let \(a^i_b\) denote vector \(a\) except with the \(i\)-th coordinate replaced with \(b_i\).

Define \[ f^{a}_i(b) = f(a^{i}_b), \] and then define \[ f^a(b) = \bigoplus_i f(a^i_b). \]

The test is as follows:

  • Sample random \(a,b\).
  • Test if \[ f^a(b) = f(b). \]

That is, test something like this:

\[ f(b_1,b_2,b_3) = f(a_1,a_2,b_3) + f(a_1,b_2,a_3) + f(b_1,a_2,a_3).\]

If the test passes with decent probability, then by choosing appropriate \(a\) we find that \(f^{a}\) is a good approximation for \(f\). But \(f^{a}\) is of course a direct sum function, so we win: \(f\) is close to a direct sum.

direct sum: Square in Cube Test

This test only uses four queries as opposed to the \(d+2\) queries of the Shapka test. However the analysis is somewhat more involved. In particular I don’t understand it yet.

Here’s the start. For \(a,b\in [n]^{d}, x\in \mathbb{F}_2^{d}\), define \(S_x(a,b)\) to be a vector in \([n]^{d}\) with \(i\)-th coordinate being \(a_i\) if \(x_i=0\) and \(b_i\) if \(x_i=1\). Let \(g\) be the function that we are testing direct-sumness of. Define \(f_{ab}(x) = g(S_x(a,b))\). Then, the Square in Cube test is as follows:

  • Sample \(a,b\gets [n]^{d},x,y\gets \mathbb{F}_2^{d}\).
  • Check: \[ f_{ab}(0)+f_{ab}(x)+f_{ab}(y) +f_{ab}(x+y) = 0.\]

Now let’s analyze this. So, suppose that \(f\) passes the test with good probability. First, this means that for most \(a,b\) we have that \[ \Pr_{x,y}[f_{ab}(0)+f_{ab}(x)+f_{ab}(y) +f_{ab}(x+y) = 0] > 1-\varepsilon.\] By BLR this means that there exists \(S_{ab},c_{ab}\) such that \[\Pr_{x}[f_{ab}(x) = c_{ab}+\chi_{S_{ab}}(x)] > 1-4\varepsilon.\]

Then by some kind of coupling argument we can show that the \(S_{ab}\)’s are in some sense a direct product function of \(b\).

I don’t quite get the whole thing though.