Derandomizing space-bounded computation via pseudorandom generators and their generalizations

To what extent is randomness necessary for efficient computation? We study the problem of deterministically simulating randomized algorithms with low space overhead. The traditional approach to this problem is to try to design sufficiently powerful pseudorandom generators (PRGs). PRG constructions often provide deep insights into models of computation and have applications beyond derandomization. There are other approaches based on generalizations of the PRG concept that are potentially easier to construct yet still valuable for derandomization. One such generalization is a hitting set generator (HSG), a standard "one-sided" version of a PRG. Another such generalization, introduced recently by Braverman, Cohen, and Garg [BCG20], is a weighted pseudorandom generator (WPRG), which is similar to a PRG except probability distributions are replaced by "pseudodistributions." In this dissertation, we present new results (obtained jointly with collaborators) regarding all three of these approaches to derandomizing space-bounded algorithms.

Regarding the PRG approach, we present improved PRGs for interesting models of computation including unbounded-width permutation branching programs, read-once AC⁰ formulas, and superlinear-size constant-depth threshold circuits. The first two PRGs are unconditionally near-optimal; substantially improving the third would require a breakthrough in circuit lower bounds. Each PRG is in some way connected to derandomizing space-bounded algorithms.

Regarding generalizations of PRGs, we present new constructions and applications of HSGs and WPRGs for read-once branching programs (ROBPs), the nonuniform model that directly corresponds to randomized space-bounded algorithms. In particular, we construct explicit HSGs and WPRGs with an optimal dependence on the error parameter ε. In terms of applications, we show that optimal HSGs for polynomial-width ROBPs could be used to derandomize decision algorithms with two-sided error (BPL, not just RL). Unconditionally, we explain how to use recent WPRG constructions to deterministically simulate randomized space-S decision algorithms in space O (S [superscript 3/2] / [square root of log S]), a slight improvement over Saks and Zhou's celebrated O (S [superscript 3/2]) bound [SZ99]. Finally, using the techniques underlying our HSG construction, we give an improved unconditional derandomization of log-space algorithms that have one-sided error and low success probability.