Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with $BPP$:
TR00-004 | 14th January 2000
Oded Goldreich, Salil Vadhan, Avi Wigderson

Simplified derandomization of BPP using a hitting set generator.

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 ... more >>>

ISSN 1433-8092 | Imprint