ECCC-Report TR00-004https://eccc.weizmann.ac.il/report/2000/004Comments and Revisions published for TR00-004en-usThu, 20 Jan 2000 10:18:42 +0200
Paper TR00-004
| Simplified derandomization of BPP using a hitting set generator. |
Oded Goldreich,
Salil Vadhan,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2000/004
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.
Thu, 20 Jan 2000 10:18:42 +0200https://eccc.weizmann.ac.il/report/2000/004