# Is being fooled by limited independence preserved by products?

Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for any $k$-wise independent random variable $X$, $\left|\mathbb{E}[f(X)] - \mathbb{E}[f(U)]\right| \le \varepsilon$ (where $U$ is uniform) and likewise for $g$. Define $h(x,y) = f(x) \cdot g(y)$. Is $h$ necessarily $O(\varepsilon)$-fooled by $O(k)$-wise independence?

If $\varepsilon=0$, the answer is yes: The hypotheses imply that $f$ and $g$ are polynomials of degree at most $k$, which implies $h$ has degree at most $2k$ and is therefore fooled by $2k$-wise independence.

This feels like it shouldn't be too hard to answer. Any ideas?

There is an equivalent formulation in terms of sandwiching polynomials (see e.g. [Bazzi07] $\S 1.1$): Essentially, it asks is the product of two "almost" degree-$k$ functions "almost" degree $O(k)$?

Equivalent Question. Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$. Suppose there exist polynomials $f_+,f_-,g_+,g_- : \{\pm 1\}^n \to \mathbb{R}$ of degree at most $k$ such that $$f_-(x) \le f(x) \le f_+(x) ~~~ \text{and} ~~~ g_-(x) \le g(x) \le g_+(x)$$ for all $x \in \{\pm 1\}^n$ and $$\mathbb{E}[f_+(U)-f_-(U)] \le \varepsilon ~~~\text{and}~~~ \mathbb{E}[g_+(U)-g_-(U)] \le \varepsilon.$$ Do there exist polynomials $h_+, h_- : \{\pm 1\}^{n} \times \{\pm 1\}^{n} \to \mathbb{R}$ of degree $O(k)$ such that $h_-(x,y) \le f(x) \cdot g(y) \le h_+(x,y)$ for all $x,y \in \{\pm 1\}^n$ and $\mathbb{E}[h_+(U,U')-h_-(U,U')] \le O(\varepsilon)$?

The obvious thing to try is setting $h_\pm(x,y)=f_\pm(x) \cdot g_\pm(y)$. Unfortunately, it doesn't seem to work out (essentially the signs and inequalities don't go the right way).

I'm also interested in generalisations of this question, where $X$ is, say, small-biased, rather than $k$-wise independent.

• If it were true that $f$ is fooled by $k$-wise independence iff its Fourier spectrum is concentrated on the first $k$ levels, then you'd be able to prove your claim by analyzing the Fourier spectrum of $f \cdot g$ and seeing that it's concentrated on the first $2k$ levels. The iff I mentioned is not true, but maybe it's true for almost $k$-wise independence or something. – mobius dumpling Mar 24 '14 at 7:32
• Similarly, the property of $f$ being fooled by $\epsilon$-biased distributions is closely related to the property $\sum_S \left|\hat{f}(S)\right| \le O(1/\epsilon)$. This latter property is preserved by products. – mobius dumpling Mar 24 '14 at 8:24

The proof goes via sandwiching polynomials. It's a simple modification of a proof in [GMRTV12] $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)