A New General Derandomization Method

We show that quick hitting set generators can replace quick pseudorandom generators to derandomize any probabilistic two-sided error algorithms. Up to now quick hitting set generators have been known as the general and uniform derandomization method for probabilistic one-sided error algorithms, while quick pseudorandom generators as the generators as the general and uniform method to derandomize probabilistic two-sided error algorithms.Our method is based on a deterministic algorithm that, given a Boolean circuit C and given access to a hitting set generator, constructs a discrepancy set for C. The main novelty is that the discrepancy set depends on C, so the new derandomization method is not uniform (i.e., not oblivious).The algorithm works in time exponential in k(p(n)) where k(*) is the price of the hitting set generator and p(*) is a polynomial function in the size of C. We thus prove that if a logarithmic price quick hitting set generator exists then BPP = P.