<p>I have figured out that the answer to this question is yes.</p>

<p>The proof goes via sandwiching polynomials. It's a simple modification of a proof in <a href="http://arxiv.org/pdf/1210.0049v1.pdf" rel="nofollow">[GMRTV12]</a> $\S 4$. (Instead of keeping track of $\mathrm{L}_1$, we keep track of degree.)</p>

CC BY-SA 3.0
2014-03-25T00:30:01.507Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-03-24T16:45:38.483Z
2014-03-24T16:45:38.483Z
Thomas Steinke
<blockquote>
<b>Question.</b> Let $f,g : \{\pm 1\}^n \to \{\pm 1\}$ be $\varepsilon$-fooled by $k$-wise independence -- i.e. for <i>any</i> $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?
</blockquote>

<p>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.</p>

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

<p>There is an equivalent formulation in terms of sandwiching polynomials (see e.g. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.1630&amp;rep=rep1&amp;type=pdf" rel="nofollow">[Bazzi07]</a> $\S 1.1$): Essentially, it asks is the product of two "almost" degree-$k$ functions "almost" degree $O(k)$?</p>

<blockquote> <b>Equivalent Question.</b>
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)$?
</blockquote>

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

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

CC BY-SA 3.0
2014-03-24T07:32:17.293Z
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.
greg
CC BY-SA 3.0
2014-03-24T08:24:01.450Z
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.
greg
<fourier-analysis><pseudorandomness><limited-independence>
Is being fooled by limited independence preserved by products?
Thomas Steinke
# Is being fooled by limited independence preserved by products?

(Asked by: username_0 on 2014-03-24)

> **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]](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.118.1630&rep=rep1&type=pdf) $\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.

**Tags:** fourier-analysis, pseudorandomness, limited-independence
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_0 on 2014-03-24. Score: 3

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]](http://arxiv.org/pdf/1210.0049v1.pdf) $\S 4$. (Instead of keeping track of $\mathrm{L}\_1$, we keep track of degree.)

> **Comments:**
> **username_2**: 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.  

---

