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.

  • 1
    $\begingroup$ 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. $\endgroup$
    – greg
    Commented Mar 24, 2014 at 7:32
  • $\begingroup$ 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. $\endgroup$
    – greg
    Commented Mar 24, 2014 at 8:24

1 Answer 1


I have figured out that the answer to this question is yes.

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

  • 1
    $\begingroup$ As such, this answer might be ok for you. But for posterity (or at least someone else who might want an answer) could you expand a little on it ? Otherwise it might be better to move this to a comment. $\endgroup$ Commented Mar 25, 2014 at 0:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.