Oded Goldreich, Salil Vadhan, Avi Wigderson

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