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, whil...

Disgrifiad llawn

Manylion Llyfryddiaeth

Cyhoeddwyd yn:	Journal of the ACM 45, 1 (1998).
Prif Awdur:	Andreev, Alexander E.
Fformat:	Erthygl
Iaith:	English
Pynciau:	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.