Next: Interleaved Zero-Knowledge in the
Up: Back at Weizmann (1998-2003)
Previous: Improved Testing Algorithms for
A hitting-set generator is an algorithm that generates a set of strings
that hit any sufficiently dense set that is recognizable by a small circuit.
Andreev, Clementi, Rolin and Trevisan showed that if
polynomial-time hitting-set generators exist then BPP equals P.
This work simplify and tighten their argument.
Comments:
Authored by O. Goldreich and A. Wigderson. Appeared in
- Random99, Springer LNCS, Vol. 1671, pages 131-137.
Oded Goldreich
2003-07-30