{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T12:10:10Z","timestamp":1763467810668},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_24","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"272-284","source":"Crossref","is-referenced-by-count":34,"title":["On Pseudorandom Generators in NC0"],"prefix":"10.1007","author":[{"given":"Mary","family":"Cryan","sequence":"first","affiliation":[]},{"given":"Peter Bro","family":"Miltersen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"issue":"2","key":"24_CR1","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1006\/jcss.1998.1583","volume":"57","author":"M. Agrawal","year":"1998","unstructured":"M. Agrawal, E. Allender and S. Rudich, \u201cReductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem\u201d; Journal of Computer and System Sciences, Vol 57(2): pages 127\u2013143, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"24_CR2","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali, \u201cHow to Generate Cryptographically Strong Sequences of Pseudo-Random Bits\u201d; SI AM Journal on Computing, Vol 13: pages 850\u2013864, 1984.","journal-title":"SI AM Journal on Computing"},{"key":"24_CR3","volume-title":"Extremal Graph Theory","author":"B. Bollab\u00e1s","year":"1978","unstructured":"B. Bollab\u00e1s, Extremal Graph Theory; Academic Press Inc (London), 1978."},{"key":"24_CR4","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company (1979)."},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"O. Goldreich, Modern Cryptography, Probabilistic Proofs and Pseudo-randomness; Vol 17 of series on Algorithms and Combinatorics, Springer-Verlag, 1999.","DOI":"10.1007\/978-3-662-12521-2"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"O. Goldreich and L. A. Levin, \u201cHard-Core Predicates for any One-Way Function\u201d; Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 25\u201332, 1989.","DOI":"10.1145\/73007.73010"},{"key":"24_CR7","unstructured":"G. R. Grimmett and D. R. Stirzaker, Probability and Random Processes, Oxford University Press, 1992."},{"issue":"4","key":"24_CR8","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J. H\u00e5stad","year":"1999","unstructured":"J. H\u00e5stad, R. Impagliazzo, L. A. Levin and M. Luby, \u201cA Pseudorandom Generator from any One-way Function\u201d; SI AM Journal on Computing, Vol 28(4): pages 1364\u20131396, 1999.","journal-title":"SI AM Journal on Computing"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. A. Levin and M. Luby, \u201cPseudo-random Generation from Oneway Functions\u201d; Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 12\u201324, 1989.","DOI":"10.1145\/73007.73009"},{"issue":"4","key":"24_CR10","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s001459900012","volume":"9","author":"R. Impagliazzo","year":"1996","unstructured":"R. Impagliazzo, M. Naor, \u201cEfficient Cryptographic Schemes Provably as Secure as Subset Sum\u201d; Journal of Cryptology, 9(4): pages 199\u2013216, 1996.","journal-title":"Journal of Cryptology"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"M. Kharitonov, \u201cCryptographic Hardness of Distribution-specific Learning\u201d; Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pages 372\u2013381, 1993.","DOI":"10.1145\/167088.167197"},{"key":"24_CR12","doi-asserted-by":"crossref","unstructured":"M. Kharitonov, A. V. Goldberg and M. Yung, \u201cLower Bounds for Pseudorandom Number Generators\u201d; Proceedings of the 30th Annual Symposium on Foundations of Computer Science, pages 242\u2013247, 1989.","DOI":"10.1109\/SFCS.1989.63485"},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"M. Krause and S. Lucks, \u201cOn the minimal Hardware Complexity of Pseudorandom Function Generators\u201d, Proceedings of the 18th Symposium on Theoretical Aspects of Computer Science, 2001.","DOI":"10.1007\/3-540-44693-1_37"},{"issue":"3","key":"24_CR14","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1145\/174130.174138","volume":"40","author":"N. Linial","year":"1993","unstructured":"N. Linial, Y. Mansour and N. Nisan, \u201cConstant Depth Circuits, Fourier Transform, and Learnability\u201d, Journal of the ACM, Vol 40(3): pages 607\u2013620, 1993.","journal-title":"Journal of the ACM"},{"key":"24_CR15","first-page":"148","volume":"141","author":"C. McDiarmid","year":"1989","unstructured":"C. McDiarmid, \u201cOn the method of bounded differences\u201d, London Mathematical Society Lecture Note Series 141, Cambridge University Press, 1989, 148\u2013188.","journal-title":"London Mathematical Society Lecture Note Series"},{"issue":"2","key":"24_CR16","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M. Naor","year":"1999","unstructured":"M. Naor and O. Reingold, \u201cSynthesizers and Their Application to the Parallel Construction of Pseudorandom Functions\u201d, Journal of Computer and Systems Sciences, 58(2): pages 336\u2013375, 1999.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"24_CR17","unstructured":"C. H. Papadimitriou, Computational Complexity; Addison-Wesley, 1994."},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"A.C.C. Yao, \u201cTheory and Applications of Trapdoor Functions\u201d; Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, pages 80\u201391, 1982.","DOI":"10.1109\/SFCS.1982.45"},{"key":"24_CR19","unstructured":"X. Yu and M. Yung, \u201cSpace Lower-Bounds for Pseudorandom-Generators\u201d; Proceedings of the Ninth Annual Structure in Complexity Theory Conference, pages 186\u2013197, 1994."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T13:27:52Z","timestamp":1556803672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}