Erratum: In Lemma 2, the
space complexity should be O(s + log w + log(1/δ)
+ log(1/γ)). That is, there is a missing O(log(1/δ))
term in the lemma statement. This does not
affect anything else in the paper.
Summary for curious non-experts:
There's a well-known conjecture in complexity theory
("L = BPL") that says that randomness isn't useful for
solving problems using a small amount of computer memory.
The most promising approach to proving this conjecture is to
design a suitable kind of "pseudorandom generator". But in
principle, one could hope to prove L = BPL using a totally
different approach. In this paper, we prove a theorem that
can be roughly stated as follows. If every true statement
along the lines of L = BPL can be proven using the
pseudorandom generator approach, then in fact L = BPL
(actually the conclusion is slightly weaker).
Versions:
The
STOC proceedings version
and the
arXiv version are the same except for formatting.
Resources:
I presented this paper at Dagstuhl Seminar 16411; the
slides are available
here.
I presented this paper at STOC 2017; the slides are available
here, and
the poster is available
here.
Notes: This paper was invited to the SIAM Journal
of Computing special issue for STOC 2017.