Skip to main content
Share Your Experience: Take the 2024 Developer Survey
10 votes

Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

For notational convenience define r.v.s $T_S = \min\{i : |S_i| = 1\}$ (recalling $S_i = S \cap H_1 \cap \cdots \cap H_i$), and $T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$. ...
Neal Young's user avatar
  • 10.8k
6 votes

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It would be a very interesting result if one were able to present a language in BPP that is hard for RP (equivalently, for co-RP) under poly-time Turing reducibility (aka Cook reducibility). I'm ...
Eric Allender's user avatar
2 votes

Parity of the sum of pseudorandom bits over a non-sparse set of inputs

You can't say anything useful. Let $E$ be a pseudorandom permutation on $\{0,1\}^m$ with $n$-bit key, $m$ be large (at least twice the security parameter), $S=\{0,1\}^m$, and define $F$ by $$F(v,w) = ...
D.W.'s user avatar
  • 12.1k
2 votes

Do pseudo-random number generator test batteries have any theoretical grounding?

But is there any theoretical motivation, why this should work? They absolutely have theoretical grounding, they are all statistical tests that any true random oracle should satisfy. It 'works', ...
orlp's user avatar
  • 885

Only top scored, non community-wiki answers of a minimum length are eligible