00000cab a22000003a 4500 UP-99796217608727534 Buklod 20231007234724.0 m |o d | ta 090226s xx d | ||r ||||| || (iLib)UPD-00077096448 DENGII eng Andreev, Alexander E. A new general derandomization method. pp. 179-213 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. Theory of computation. Analysis of algorithms and problem complexity. Nonnumerical algorithms and problems. Computations on discrete structures. Mathematics of computing. Probability and statistics. Probabilistic algorithms (including Monte Carlo). Algorithms. Theory. Journal of the ACM 45, 1 (1998). FO UPD DENG-II Article