Algorithmic derandomization via complexity theory

Abstract

We point out how the methods of Nisan [31, 32], originally developed for derandomizing space-bounded computations, may be applied to obtain polynomial-time and NC derandomizations of several probabilistic algorithms. Our list includes the randomized rounding steps of linear and semi-definite programming relaxations of optimization problems, parallel derandomization of discrepancy-type problems, and the Johnson-Lindenstrauss lemma, to name a few. A fascinating aspect of this style of derandomization is the fact that we often carry out the derandomizations directly from the statements about the correctness of probabilistic algorithms, rather than carefully mimicking their proofs.