Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this assumption that BPL ⊆ ∩ α > 0 DSPACE (log 1 + α n ).

Authors

• William M. Hoza
• Chris Umans

Keywords

• derandomization
• pseudorandom generators
• space complexity