ECCC-Report TR95-061https://eccc.weizmann.ac.il/report/1995/061Comments and Revisions published for TR95-061en-usFri, 09 Feb 1996 00:00:00 +0200
Revision 1
| Hitting Sets Derandomize BPP Revision of: TR95-061 |
A. E. Andreev,
Andrea E. F. Clementi,
Jose' D. P. Rolim
https://eccc.weizmann.ac.il/report/1995/061#revision1We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the output of any boolean
circuit of polynomial size.
This new algorithm implies that if a quick hitting set generator
with logarithmic price exists then BPP=P. Furthermore,
the algorithm can be applied in order to show that the existence
of a quick hitting set generator with price k implies that
BPTIME(t) <= DTIME(2^{O(k(t^{O(1)}))}).
The existence of quick hitting set generators is thus a new
weaker sufficient condition to obtain BPP=P.
Fri, 09 Feb 1996 00:00:00 +0200https://eccc.weizmann.ac.il/report/1995/061#revision1
Paper TR95-061
| Hitting sets derandomize BPP |
Alexander E. Andreev,
Andrea E. F. Clementi,
Jose' D. P. Rolim
https://eccc.weizmann.ac.il/report/1995/061We show that hitting sets can derandomize any BPP-algorithm.
This gives a positive answer to a fundamental open question in
probabilistic algorithms. More precisely, we present a polynomial
time deterministic algorithm which uses any given hitting set
to approximate the fractions of 1's in the output of any boolean
circuit of polynomial size.
This new algorithm implies that if a quick hitting set generator
with logarithmic price exists then BPP=P. Furthermore, we
generalize this result by showing that the existence of a quick
hitting set generator with price k implies that
BPTIME(t) <= DTIME(2^{O(k(t^{O(1)}))}).
The existence of quick hitting set generators is thus a new
weaker sufficient condition to obtain BPP=P; this can be
considered as another strong indication that the gap between
probabilistic and deterministic computational power is not large.
Wed, 06 Dec 1995 19:25:21 +0200https://eccc.weizmann.ac.il/report/1995/061