##
Simplified Derandomization of BPP using a Hitting Set Generator

Oded Goldreich
, Salil Vadhan, and Avi Wigderson.

###
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 et al. (ICALP'96, and JACM 1998) showed that a polynomial-time
hitting-set generator in fact implies the much stronger conclusion BPP=P.
We simplify and improve their (and later) constructions.

###
Versions

[ back to
Salil Vadhan's research interests ]