zbMATH — the first resource for mathematics

Simplified derandomization of BPP using a hitting set generator. (English) Zbl 1343.68303
Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 59-67 (2011).
Summary: A hitting-set generator is a deterministic algorithm that generates a set of strings such that this set intersects every dense set that is recognizable by a small circuit. A polynomial time hitting-set generator readily implies \(\mathcal{RP}=\mathcal{P}\), but it is not apparent what this implies for \(\mathcal{BPP}\). Nevertheless, A. E. Andreev et al. [Lect. Notes Comput. Sci. 1099, 357–368 (1996; Zbl 1046.68536); J. ACM 45, No. 1, 179–213 (1998; Zbl 0903.68089)] showed that a polynomial-time hitting-set generator implies the seemingly stronger conclusion \(\mathcal{BPP=P}\). We simplify and improve their (and later) constructions.
For the entire collection see [Zbl 1220.68005].

68W20 Randomized algorithms
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDF BibTeX Cite
Full Text: DOI
[1] Adleman, L.: Two theorems on random polynomial-time. In: 19th FOCS, pp. 75–83 (1978)
[2] Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P.: A new general derandomization method. Journal of the Association for Computing Machinery (J. of ACM) 45(1), 179–213 (1998); Hitting Sets Derandomize BPP. In: XXIII International Colloquium on Algorithms, Logic and Programming, ICALP 1996 (1996) · Zbl 0903.68089
[3] Andreev, A.E., Clementi, A.E.F., Rolim, J.D.P., Trevisan, L.: Weak Random Sources, Hitting Sets, and BPP Simulations. To appear in SICOMP (1997); Preliminary version in 38th FOCS, pp. 264–272 (1997) · Zbl 0943.68064
[4] Buhrman, H., Fortnow, L.: One-sided versus two-sided randomness. In: Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science. LNCS, Springer, Berlin (1999) · Zbl 0928.68052
[5] Even, S., Selman, A.L., Yacobi, Y.: The Complexity of Promise Problems with Applications to Public-Key Cryptography. Inform. and Control 61, 159–173 (1984) · Zbl 0592.94012
[6] Goldreich, O., Zuckerman, D.: Another proof that BPP PH (and more). In: Goldreich, O., et al.: Studies in Complexity and Cryptography. LNCS, vol. 6650, pp. 40–53. Springer, Heidelberg (1997) · Zbl 1343.68085
[7] Goldreich, O., Wigderson, A.: Improved derandomization of BPP using a hitting set generator. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol. 1671, pp. 131–137. Springer, Heidelberg (1999)
[8] Impagliazzo, R., Wigderson, A.: P=BPP unless E has Subexponential Circuits: Derandomizing the XOR Lemma. In: 29th STOC, pp. 220–229 (1997) · Zbl 0962.68058
[9] Lautemann, C.: BPP and the Polynomial Hierarchy. Information Processing Letters 17, 215–217 (1983) · Zbl 0515.68042
[10] Sipser, M.: A complexity-theoretic approach to randomness. In: 15th STOC, pp. 330–335 (1983)
[11] Zuckerman, D.: Simulating BPP Using a General Weak Random Source. Algorithmica 16, 367–391 (1996) · Zbl 0857.68121
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.