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 ]