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")...
  • 7,090
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 ...
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 ...
10 votes

Pseudorandom generator for finite automata

If $d$ is of the order of $n$ then you can write a constant-width branching program as a finite-state automaton, and logarithmic seed length is not known. But if $d$ is very small, say a constant, ...
  • 7,509
7 votes
Accepted

Pseudorandom generators indistinguishable by uniform deterministic adversaries

Yes, this notion has been studied. One interesting aspect is that the two notions of pseudorandomness known to be equivalent under the usual adversaries, "next bit predictability" and "...
4 votes

Random flows through fixed network

Not very practical, but you can sample from a the polytope of feasible flows using the well-known random walk techniques, see for example this classical paper by Kannan, Lovasz and Simonovits. These ...
2 votes
Accepted

Generating uniform integers in a range from a random generator with another range

I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy. Description of the scheme. Thinking as an ...
  • 7,485
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)}$ ...
1 vote

Pseudorandom generator for finite automata

something close to what you are requesting seems to be proven in Thm 2.10 p6 of these lecture notes by O'Donnell, Lecture 16: Nisan’s PRG for small space but it does not cite the original ref for the ...
  • 10.9k

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