7
$\begingroup$

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?

$\endgroup$
  • 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 '13 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$ – Akshay Oct 24 '13 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 '13 at 17:57
  • $\begingroup$ I guess "efficiently computable" is not clear itself. $\endgroup$ – Sasho Nikolov Oct 24 '13 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$ – Thomas supports Monica Oct 25 '13 at 5:16
11
$\begingroup$

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

$\endgroup$
  • $\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 '13 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$ – usul Oct 23 '13 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$ – Thomas supports Monica Oct 23 '13 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 '13 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$ – usul Oct 23 '13 at 18:03

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.