Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-004 | 14th January 2000 00:00

Simplified derandomization of BPP using a hitting set generator.

RSS-Feed




TR00-004
Authors: Oded Goldreich, Salil Vadhan, Avi Wigderson
Publication: 20th January 2000 10:18
Downloads: 2140
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