# ​​​​​The residents of Newton vs. the marijuana industry: 1-1

With a historic effort, the residents of Newton MA have collected in a very short time 6,000+ signatures thanks to which a forthcoming ballot will include a question on banning recreational Marijuana sales in the city. (For background see the previous post and comments.)

# bounded independence plus noise fools space

There are many classes of functions on $n$ bits that we know are fooled by bounded independence, including small-depth circuits, halfspaces, etc. (See this previous post.)

On the other hand the simple parity function is not fooled. It’s easy to see that you require independence at least $n-1$. However, if you just perturb the bits with a little noise $N$, then parity will be fooled. You can find other examples of functions that are not fooled by bounded independence alone, but are if you just perturb the bits a little.

In  we proved that any distribution with independence about $n^{2/3}$ fools space-bounded algorithms, if you perturb it with noise. We asked, both in the paper and many people, if the independence could be lowered. Forbes and Kelley have recently proved  that the independence can be lowered all the way to $O(\log n)$, which is tight . Shockingly, their proof is nearly identical to !

This exciting result has several interesting consequences. First, we now have almost the same generators for space-bounded computation in a fixed order as we do for any order. Moreover, the proof greatly simplifies a number of works in the literature. And finally, an approach in  to prove limitations for the sum of small-bias generators won’t work for space (possibly justifying some optimism in the power of the sum of small-bias generators).

My understanding of all this area is inseparable from the collaboration I have had with Chin Ho Lee, with whom I co-authored all the papers I have on this topic.

### The proof

Let $f:\{0,1\}^{n}\to \{0,1\}$ be a function. We want to show that it is fooled by $D+E$, where $D$ has independence $k$, $E$ is the noise vector of i.i.d. bits coming up $1$ with probability say $1/4$, and $+$ is bit-wise XOR.

The approach in  is to decompose $f$ as the sum of a function $L$ with Fourier degree $k$, and a sum of $t$ functions $H_{i}=h_{i}\cdot g_{i}$ where $h_{i}$ has no Fourier coefficient of degree less than $k$, and $h_{i}$ and $g_{i}$ are bounded. The function $L$ is immediately fooled by $D$, and it is shown in  that each $H_{i}$ is fooled as well.

To explain the decomposition it is best to think of $f$ as the product of $\ell :=n/k$ functions $f_{i}$ on $k$ bits, on disjoint inputs. The decomposition in  is as follows: repeatedly decompose each $f_{i}$ in low-degree $f_{L}$ and high-degree $f_{H}$. To illustrate: \begin{aligned} f_{1}f_{2}f_{3} & =f_{1}f_{2}(f_{3H}+f_{3L})=f_{1}f_{2}f_{3H}+f_{1}(f_{2H}+f_{2L})f_{3L}=\ldots \\ = & f_{1H}f_{2L}f_{3L}+f_{1}f_{2H}f_{3L}+f_{1}f_{2}f_{3H}+f_{1L}f_{2L}f_{3L}\\ = & H_{1}+H_{2}+H_{3}+L. \end{aligned}

This works, but the problem is that even if each time $f_{iL}$ has degree $1$, the function $L$ increases the degree by at least $1$ per decomposition; and so we can afford at most $k$ decompositions.

The decomposition in  is instead: pick $L$ to be the degree $k$ part of $f$, and $H_{i}$ are all the Fourier coefficients which are non-zero in the inputs to $f_{i}$ and whose degree in the inputs of $f_{1},\ldots ,f_{i}$ is $\ge k$. The functions $H_{i}$ can be written as $h_{i}\cdot g_{i}$, where $h_{i}$ is the high-degree part of $f_{1}\cdots f_{i}$ and $h_{i}$ is $f_{i+1}\cdots f_{\ell }$.

Once you have this decomposition you can apply the same lemmas in  to get improved bounds. To handle space-bounded computation they extend this argument to matrix-valued functions.

### What’s next

In  we asked for tight “bounded independence plus noise” results for any model, and the question remains. In particular, what about high-degree polynomials modulo $2$?

### References

   Ravi Boppana, Johan Håstad, Chin Ho Lee, and Emanuele Viola. Bounded independence vs. moduli. In Workshop on Randomization and Computation (RANDOM), 2016.

   Michael A. Forbes and Zander Kelley. Pseudorandom generators for read-once branching programs, in any order. In IEEE Symp. on Foundations of Computer Science (FOCS), 2018.

   Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded independence plus noise fools products. SIAM J. on Computing, 47(2):295–615, 2018.

   Chin Ho Lee and Emanuele Viola. Some limitations of the sum of small-bias distributions. Theory of Computing, 13, 2017.