20 votes

Examples of successful derandomization from BPP to P

$SL = L$. $RL$ stands for randomized logspace and $RL=L$ is a smaller version of the problem $RP=P$. A major stepping stone was the proof of Reingold in '04 ("Undirected S-T Connectivity in Logspace")...
usul's user avatar
  • 7,615
16 votes

Examples of successful derandomization from BPP to P

There is basically only one interesting problem in BPP not known to be in P: Polynomial Identity Testing, given an algebraic circuit is the polynomial it generates identically zero. Impagliazzo and ...
Lance Fortnow's user avatar
13 votes

Examples of successful derandomization from BPP to P

Besides polynomial identity testing, one other very important problem known to be in BPP but not in P is approximating the permanent of a non-negative matrix or even the number of perfect matchings in ...
Raghu Meka's user avatar
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
  • 12k
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