For a distribution X over $\{0,1\}^n$, we can define the Fourier coefficient of the distribution as $\hat{Y}(s)= \textbf{E}_{y\in Y}({\chi_s(y)})$.
The question I have is, do there exist distributions that can be efficiently computed such that at most polynomially many Fourier coefficients are non-zero?
$\begingroup$
$\endgroup$
6
-
1$\begingroup$ Akshay, would you clarify what requirements you have on the pseudorandom distribution? Do you merely require that the distribution be indistinguishable from a uniformly distributed random variable, by any polynomial-time algorithm? Do you have any additional requirements, e.g., on the amount of stretch or the size of the seed? $\endgroup$– D.W.Oct 23, 2013 at 19:33
-
$\begingroup$ @D.W. My bad, I actually require the distribution to have a small size. I don't really want it to derandomize BPP but rather constant width branching programs. I have edited the question. Thanks! $\endgroup$– AkshayOct 24, 2013 at 16:33
-
$\begingroup$ Hmm. I'm still not sure if I've got the requirements right. So you don't need the distribution to be pseudorandom? Do you need the distribution to be efficiently computable, or to have small support? The body of the question says the former, the title says the latter. Those two conditions are not equivalent. For instance, I suspect there are efficiently computable distributions that have polynomially many non-zero Fourier coefficients; but there are not distributions that have polynomially many non-zero Fourier coefficients and that have small support. $\endgroup$– D.W.Oct 24, 2013 at 17:57
-
$\begingroup$ I guess "efficiently computable" is not clear itself. $\endgroup$– Sasho NikolovOct 24, 2013 at 23:15
-
1$\begingroup$ Usually "pseudorandom distribution" means (i) it approximates the uniform distribution in some sense and (ii) it is statistically far from uniform. Here (i) is measured in terms of the sparsity of the Fourier transform (uniform has support 1). And I'm interpreting (ii) to mean small seed length. $\endgroup$– ThomasOct 25, 2013 at 5:16
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
10
If you want $Y$ to have entropy less than $0.99 n$ bits, the answer is no, by the uncertainty principle: Either $Y$ has high entropy or its Fourier transform has large support.
Theorem. Let $H(Y)$ be the Shannon entropy of $Y$ and let $F \subset \{0,1\}^n$ be the support of $\hat{Y}$. Then $H(Y) \geq n - \log |F|$.
Proof. Consider the collision probability of $Y$ (the probability that two independent samples of $Y$ are the same). By Parseval's identity, $$CP(Y) = \sum_y \text{Pr}[Y=y]^2 = 2^{-n} \sum_s \hat{Y}(s)^2 \leq 2^{-n} |F|,$$ as $|\hat{Y}(s)| \leq 1$. On the other hand, $CP(Y) = 2^{-H_2(Y)}$, where $H_2(Y)$ is the Renyi entropy of $Y$. Noting that $H_2(Y) \leq H(Y)$ gives the result. Q.E.D.
If $|F| = \mathrm{poly}(n)$, then $H(Y) = n-O(\log n)$. So, if $Y$ is the output of a pseudorandom generator, the seed length is at least $n-O(\log n)$.
-
$\begingroup$ I don't follow the reasoning here, especially the last sentence. Why does the fact that $Y$ has large support mean that it isn't pseudorandom? Actually, that sounds backwards. Indeed, I'd expect that any pseudorandom distribution had darn well better have large support, if it is to have any hope of being pseudorandom (if $|S|$ is small, then it's easy to distinguish $Y$ from random, which means the distribution isn't pseudorandom). $\endgroup$– D.W.Oct 23, 2013 at 6:22
-
1$\begingroup$ @D.W. I think we often want a much bigger stretch, e.g. we would need to stretch a $\log(n)$-bit seed to an $n$-bit output in order to derandomize BPP (but such generators would have support only of size $n$). So maybe the exact answer is "maybe, if you consider stretching $n-\log(n)$ bits to $n$ bits sufficient, no otherwise". $\endgroup$– usulOct 23, 2013 at 13:24
-
1$\begingroup$ @D.W. $\log |S|$ is a lower bound on the seed length needed to sample $Y$. One wants a pseudorandom distribution to have small seed length and thus small support. The point is that we want $Y$ to `look like' something with large support, whilst actually having sparse support. $\endgroup$– ThomasOct 23, 2013 at 14:17
-
$\begingroup$ If the seed length is $\lg n$ bits, then the generator is not pseudorandom: there is a trivial polynomial-time attack to distinguish its output from true random (simply enumerate all seeds to see if the value of $Y$ is attained by any of them, i.e., enumerate its support). $\endgroup$– D.W.Oct 23, 2013 at 17:25
-
$\begingroup$ @D.W. agreed that this was a bad example, mainly because of the efficiently sample-able requirement. I should instead have just said that we would like a PRG to stretch for instance $o(n)$-bit seeds to $n$-bit outputs. $\endgroup$– usulOct 23, 2013 at 18:03