Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATION ALGORITHMS:
Reports tagged with Approximation Algorithms:
TR95-061 | 27th November 1995
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting sets derandomize BPP

Revisions: 1

We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the ... more >>>




ISSN 1433-8092 | Imprint