Skip to main content
4 votes

Are there pseudorandom sequences which cannot be learned by any ML model but which still fail the Diehard tests?

Yes, (it is believed that) there are sequences that can't be learned by any ML model: cryptographic pseudorandom generators (see also here) are one good candidate. If a sequence fails some Diehard ...
D.W.'s user avatar
  • 12.2k
2 votes
Accepted

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.2k
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
2 votes
Accepted

Nonconstructive $\log(n)$ seed length PRG for fooling modular tests

By "possible," the authors mean that one can show that a uniformly random set of $\mathsf{poly}(n,M,1/\varepsilon)$ strings of length $n$ is a $\varepsilon$-PRG for modular tests with ...
Jason Gaitonde's user avatar
1 vote

Derandomizing arbitrary width *read-many* and *ordered* branching programs?

(Posting this as an answer because I am unable to comment.) There may be some confusion between models here. Width 5 read many branching programs capture $NC_1$, and width poly$(n)$ ordered branching ...
TedP's user avatar
  • 11
1 vote

Examples of successful derandomization from BPP to P

The Perfect Matching problem was "almost" derandomized in 2016 [1]: there is a deterministic algorithm requiring "only" quaispolynomial resources, namely $n^{\mathcal O(\log n)}$ ...
Lieuwe Vinkhuijzen's user avatar

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