# Tag Info

### 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 ...
• 12.2k
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) = ...
• 12.2k

### 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', ...
• 885
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 ...
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 ...
• 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)}$ ...
• 2,004

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