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.
