3
$\begingroup$

Let $D$ be an $\epsilon$-biased distribution we want to show that $$\text{Supp}(D)\geq \Omega\bigg(\frac{n}{\epsilon^2\log(\frac{1}{\epsilon})}\bigg)$$ I know that there are some proofs for this but I am intrested in the following particular way.

Let $X,Y$ be two distributions over $\{0,1\}^n$. Consider the "convolution" of distributions $Z=X\circledast Y$ to be defined by sampling $x\sim X$ and $y\sim Y$ independently and outputting $x\oplus y$ where $\oplus$ is just bit-wise xor.

Now if we define a distribution $D^{(t)}=D\circledast\cdots\circledast D$ ($t$ times) we can use some Fourier analysis and combinatorics to show that

  1. $D^{(t)}$ is $\epsilon^t$-biased.
  2. $|\text{Supp}(D^{(t)})|\leq\binom{|\text{Supp}(D)|+t}{t}$

We can also show that for every $\delta$-biased distribution $Z$ we have $\lVert Z\rVert_2^2\leq\delta^2+2^{-n}$ when considering the distribution as a vector of probabilities. Now, I was told that I can use the latter to obtain a lower bound on $|\text{Supp}(D^{(t)})|$ and then choose $t$ accordingly to get the desired bound.

However, the only bound I can get for $|\text{Supp}(D^{(t)})|$ is $$|\text{Supp}(D^{(t)})|\geq\sqrt{\frac{1}{\epsilon^{2t}+2^{-n}}}$$ And I don't see how that helps...

$\endgroup$
  • 1
    $\begingroup$ It's not clear what you're asking. If you're trying to understand an existing result, please cite it. Are you suggesting a novel proof, etc?.. $\endgroup$ – Aryeh Dec 29 '18 at 21:29
  • $\begingroup$ @Aryeh In some lecture notes by Swastik Kopparty (about Boolean functions and derandomization) I have seen an "exercise" consisting of four parts that asks to prove the "famous" lower bound on the support size of $\epsilon$-biased distribution. The first three parts are described above and I managed to handle with them. At the last part the exercise asks to use the first parts in order to get the lower bound, I do not understand how to do so. I do know that there is a proof not following the above line, but I am interested in the above. $\endgroup$ – user621824 Dec 30 '18 at 7:43
  • $\begingroup$ @user621824 OK, first: are you sure about the square root in your RHS? (Note that the $\ell_2$ norm of a distribution over support of size $N$ is lower bounded by $1/\sqrt{N}$; you here have the squared $\ell_2$ norm). Second: set $t$ such that the two terms of the denominator balance. Third: use $\binom{n}{k} \leq (en/k)^k$. This ought to be enough. $\endgroup$ – Clement C. Dec 30 '18 at 9:04
2
$\begingroup$
  1. You shouldn't have a square root. Namely, for every $\delta$-biased distribution $Z$ (using your notation), we have $$ \delta^2+2^{-n} \geq \lVert Z\rVert^2_2 \geq \frac{1}{\lvert\operatorname{supp} Z\rvert}\tag{1} $$ since the squared $\ell_2$ norm of a distribution over support of size $N$ is at least that of the uniform distribution on $N$ elements, which is $1/N$.

  2. This gives you, for $t\geq 1$ to choose suitably, $$\lvert\operatorname{supp} D^{(t)}\rvert \geq \frac{1}{\varepsilon^{2t}+2^{-n}} \tag{2} $$ since as you have shown $D^{(t)}$ is $\delta$-biased for $\delta=\varepsilon^t$. A natural choice of $t$, in view of (2), is the one balancing the denominator, i.e., such that $\varepsilon^{2t}=2^{-n}$. This leads to taking $$ t \stackrel{\rm def}{=} \frac{n}{2\log(1/\varepsilon)}\tag{3} $$

  3. Recalling the standard bound $\binom{n}{k}\leq \left(\frac{en}{k}\right)^k$ for $1\leq k\leq n$ along with (2), (3), and what you mentioned as 2. in your question, we thus get $$ \left(\frac{e(\lvert\operatorname{supp} D \rvert+t)}{t}\right)^t \geq \binom{\lvert\operatorname{supp} D \rvert+t}{t} \geq \frac{1}{\varepsilon^{2t}+2^{-n}} = \frac{1}{2\varepsilon^{2t}} \tag{4} $$ so that $$ \frac{e(\lvert\operatorname{supp} D \rvert+t)}{t} \geq \frac{1}{2^{1/t}\varepsilon^{2}} \tag{5} $$

Rearranging and recalling again the choice of $t$ in (3) yields $$ \lvert\operatorname{supp} D \rvert\geq \Omega\!\left(\frac{n}{\varepsilon^{2}\log(1/\varepsilon)} \right) \tag{6} $$ as claimed.

$\endgroup$
  • $\begingroup$ Sorry for not accepting for a long time. Thank you! $\endgroup$ – user621824 Jan 2 at 16:24
  • $\begingroup$ @user621824 No problem at all. Glad this helped. $\endgroup$ – Clement C. Jan 2 at 16:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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