Abstract
The construction of pseudo-random generators (PRGs) has been based on strong assumptions like the existence of one-way functions or exponential lower bounds for the circuit complexity of Boolean functions. Given our current lack of satisfactory progress towards proving these assumptions, we study the implications of constructing PRGs for weaker models of computation to the derandomization of general classes like BPP. More specifically, we show how PRGs that fool monotone circuits could lead to derandomization for general complexity classes, and how the Nisan-Wigderson construction could use hardness results for monotone circuits to produce pseudo-random strings.
Research supported by an NSERC Discovery grant.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Amano, K., Maruoka, A.: Potential of the approximation method. In: 37th FOCS, pp. 431–440 (1996)
Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity 3(4), 307–318 (1993)
Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. on computing 13(4), 850–864 (1984)
Harnik, D., Raz, R.: Higher Lower Bounds for Monotone Size. In: 32nd STOC, pp. 191-201 (2000)
Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: 36th FOCS (1995)
Impagliazzo, R., Kabanets, V.: Derandomizing Polynomial Identity Tests means proving circuit lower bounds. In: 35th STOC (2003) (to appear)
Impagliazzo, R., Levin, L., Luby, M.: Pseudorandom generators from any one-way function. In: 21st STOC (1989)
Impagliazzo, R., Shaltiel, R., Wigderson, A.: Near-optimal conversion of hardness into pseudo-randomness. In: 40th FOCS, pp. 181–190 (1999)
Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits. In: 29th STOC, pp. 220–229 (1998)
Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. on Discrete Mathematics 3(2), 255–265 (1990)
Nisan, N., Wigderson, A.: Hardness vs. Randomness. JCSS 49(2), 149–167 (1994)
O’Donnell, R.: Hardness Amplification Within NP. In: 34th STOC, pp. 751–760 (2002)
Raz, R., McKenzie, P.: Separation of the Monotone NC Hierarchy. Combinatorica 19(3), 403–435 (1999)
Razborov, A.: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk. SSSR 281(4), 598–607 (1985) (In Russian)
Shamir, A.: On the generation of cryptographically strong pseudo-random sequences. In: Even, S., Kariv, O. (eds.) ICALP 1981. LNCS, vol. 115. Springer, Heidelberg (1981)
Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. In: 31st STOC, pp. 537–546 (1999)
Wegener, I.: The complexity of Boolean functions. John Wiley, Chichester (1987)
Yao, A.C.: Theory and applications of trapdoor functions. In: 23rd FOCS, pp. 80–91 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karakostas, G. (2009). General Pseudo-random Generators from Weaker Models of Computation. In: Dong, Y., Du, DZ., Ibarra, O. (eds) Algorithms and Computation. ISAAC 2009. Lecture Notes in Computer Science, vol 5878. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10631-6_110
Download citation
DOI: https://doi.org/10.1007/978-3-642-10631-6_110
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10630-9
Online ISBN: 978-3-642-10631-6
eBook Packages: Computer ScienceComputer Science (R0)