Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR00-004 | 14th January 2000 00:00

#### Simplified derandomization of BPP using a hitting set generator.

TR00-004
Authors: Oded Goldreich, Salil Vadhan, Avi Wigderson
Publication: 20th January 2000 10:18
Keywords:

Abstract:

A hitting-set generator is a deterministic
algorithm which generates a set of strings that intersects
every dense set recognizable by a small circuit.
A polynomial time hitting-set generator readily implies \$RP=P\$.
Andreev \etal\/ (ICALP'96, and JACM 1998)
showed that if polynomial-time hitting-set
generator in fact implies the much stronger conclusion \$BPP=P\$.
We simplify and improve their (and later) constructions.

ISSN 1433-8092 | Imprint