Skip to main content
Springer Nature Link
Log in

General Pseudo-random Generators from Weaker Models of Computation

  • Conference paper
Algorithms and Computation (ISAAC 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5878))

Included in the following conference series:

  • 1857 Accesses

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

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Amano, K., Maruoka, A.: Potential of the approximation method. In: 37th FOCS, pp. 431–440 (1996)

    Google Scholar 

  2. 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)

    Article  MATH  MathSciNet  Google Scholar 

  3. Blum, M., Micali, S.: How to generate cryptographically strong sequences of pseudo-random bits. SIAM J. on computing 13(4), 850–864 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  4. Harnik, D., Raz, R.: Higher Lower Bounds for Monotone Size. In: 32nd STOC, pp. 191-201 (2000)

    Google Scholar 

  5. Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: 36th FOCS (1995)

    Google Scholar 

  6. Impagliazzo, R., Kabanets, V.: Derandomizing Polynomial Identity Tests means proving circuit lower bounds. In: 35th STOC (2003) (to appear)

    Google Scholar 

  7. Impagliazzo, R., Levin, L., Luby, M.: Pseudorandom generators from any one-way function. In: 21st STOC (1989)

    Google Scholar 

  8. Impagliazzo, R., Shaltiel, R., Wigderson, A.: Near-optimal conversion of hardness into pseudo-randomness. In: 40th FOCS, pp. 181–190 (1999)

    Google Scholar 

  9. Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits. In: 29th STOC, pp. 220–229 (1998)

    Google Scholar 

  10. Karchmer, M., Wigderson, A.: Monotone circuits for connectivity require super-logarithmic depth. SIAM J. on Discrete Mathematics 3(2), 255–265 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  11. Nisan, N., Wigderson, A.: Hardness vs. Randomness. JCSS 49(2), 149–167 (1994)

    MATH  MathSciNet  Google Scholar 

  12. O’Donnell, R.: Hardness Amplification Within NP. In: 34th STOC, pp. 751–760 (2002)

    Google Scholar 

  13. Raz, R., McKenzie, P.: Separation of the Monotone NC Hierarchy. Combinatorica 19(3), 403–435 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  14. Razborov, A.: Lower bounds on the monotone complexity of some Boolean functions. Dokl. Akad. Nauk. SSSR 281(4), 598–607 (1985) (In Russian)

    MathSciNet  Google Scholar 

  15. 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)

    Google Scholar 

  16. Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. In: 31st STOC, pp. 537–546 (1999)

    Google Scholar 

  17. Wegener, I.: The complexity of Boolean functions. John Wiley, Chichester (1987)

    MATH  Google Scholar 

  18. Yao, A.C.: Theory and applications of trapdoor functions. In: 23rd FOCS, pp. 80–91 (1982)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computing and Software, McMaster University, 1280 Main St. West, Hamilton, Ontario, L8S 4K1, Canada

    George Karakostas

Authors
  1. George Karakostas
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. of Electrical and Computer Engineering, University of Hawaii, Holmes Hall 483, 2540 Dole Street, 96822, Honolulu, HI, USA

    Yingfei Dong

  2. Department of Computer Science, University of Texas at Dallas, 75083, Dallas, TX, USA

    Ding-Zhu Du

  3. Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA

    Oscar Ibarra

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics

Search

Navigation