Erratum (May 2017): 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.
Not-so-abstract:
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.
Study 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.
Due to a mix-up, at the time of this writing (11/26/17), a
video of the STOC presentation of this paper can be found at
the ACM digital library page for an unrelated paper by Cai
and Zhao.
Notes: This paper was invited to the SIAM Journal
of Computing special issue for STOC 2017. Oded Goldreich has
commented
on this paper.