Physical Sciences and Mathematics Commons^™

Exploring Improvements To Space-Bounded Derandomization From Better Pseudorandom Generators, Boxian Wang

Computer Science Senior Theses

Saks and Zhou used Nisan’s PRG in a recursive manner to obtain BPL ⊆ L^(3/2). We describe how this framework could be generalized to use arbitrary PRGs following Armoni’s sampler idea. We then give a theorem relating the seed length of a better PRG to the implied improvements in derandomizing BPL. Recently, Hoza used Armoni’s PRG in the Saks-Zhou framework to obtain an even better derandomization. We describe the construction of Armoni’s PRG and conjecture that by using basic components other than extractors, parameters in that construction could be improved. Under some assumptions, we calculate the extent to which such …