A new general derandomization method

Publisher Website
Google Scholar
Abstract
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.

This publication has 5 references indexed in Scilit: