{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:38Z","timestamp":1725664178635},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540590422"},{"type":"electronic","value":"9783540491750"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59042-0_61","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T16:59:41Z","timestamp":1330275581000},"page":"50-59","source":"Crossref","is-referenced-by-count":0,"title":["Pseudorandom generators and the frequency of simplicity"],"prefix":"10.1007","author":[{"given":"Yenjo","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lane A.","family":"Hemaspaandra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"E. Allender. Some consequences of the existence of pseudorandom generators, preliminary version. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 151\u2013159, 1987.","DOI":"10.1145\/28395.28412"},{"key":"5_CR2","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0022-0000(89)90021-4","volume":"39","author":"E. Allender","year":"1989","unstructured":"E. Allender. Some consequences of the existence of pseudorandom generators. Journal of Computer and System Sciences, 39:101\u2013124, 1989.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"E. Allender. Applications of time-bounded kolmogorov complexity in complexity theory. In O. Watanabe, editor, Kolmogorov Complexity and Computational Complexity, EATCS Monographs on Theoretical Computer Science, pages 4\u201322. Springer-Verlag, 1992.","DOI":"10.1007\/978-3-642-77735-6_2"},{"key":"5_CR4","unstructured":"R. Boppana and R. Hirschfeld. Pseudorandom generators and complexity classes. In Advances in Computing Research, volume 5, pages 1\u201326. JAI Press Inc., 1989."},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 112\u2013117, 1982. Final version appears as [BM84].","DOI":"10.1109\/SFCS.1982.72"},{"issue":"4","key":"5_CR6","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850\u2013864, 1984.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(91)90070-I","volume":"88","author":"R. Gavald\u00e0","year":"1991","unstructured":"R. Gavald\u00e0 and J. Balc\u00e1zar. Strong and robustly strong polynomial-time reducibilities to sparse sets. Theoretical Computer Science, 88:1\u201314, 1991.","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"5_CR8","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"J. Gill. Computational complexity of probabilistic Turing machines. SIAM Journal on Computing, 6(4):675\u2013695, 1977.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"5_CR9","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1137\/0222069","volume":"22","author":"O. Goldreich","year":"1993","unstructured":"O. Goldreich, H. Krawczyk, and M. Luby. On the existence of pseudorandom generators. SIAM Journal on Computing, 22(6):1163\u20131175, 1993.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"J. Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations. In Proceedings of the 24th IEEE Symposium on Foundations of Computer Science, pages 439\u2013445. IEEE Computer Society Press, 1983.","DOI":"10.1109\/SFCS.1983.21"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad. Pseudo-random generators under uniform assumptions. In Proceedings of the 22nd ACM Symposium on Theory of Computing, pages 395\u2013404, 1990.","DOI":"10.1145\/100216.100270"},{"key":"5_CR12","unstructured":"J. Hopcroft and J. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979."},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, L. Levin, and M. Luby. Pseudo-random generation from oneway functions. In Proceedings of the 21st ACM Symposium on Theory of Computing, pages 12\u201324, 1989.","DOI":"10.1145\/73007.73009"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","volume":"61","author":"L. Levin","year":"1984","unstructured":"L. Levin. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61:15\u201337, 1984.","journal-title":"Information and Control"},{"issue":"4","key":"5_CR15","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579323","volume":"7","author":"L. Levin","year":"1987","unstructured":"L. Levin. One way functions and pseudorandom generators. Combinatorica, 7(4):357\u2013363, 1987.","journal-title":"Combinatorica"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"M. Li and P. Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, 1993.","DOI":"10.1007\/978-1-4757-3860-5"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330\u2013335, 1983.","DOI":"10.1145\/800061.808762"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"A. Yao. Theory and applications of trapdoor functions. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pages 80\u201391, 1982.","DOI":"10.1109\/SFCS.1982.45"},{"key":"5_CR19","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0019-9958(86)80044-4","volume":"69","author":"S. Zachos","year":"1986","unstructured":"S. Zachos and H. Heller. A decisive characterization of BPP. Information and Control, 69:125\u2013135, 1986.","journal-title":"Information and Control"}],"container-title":["Lecture Notes in Computer Science","STACS 95"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59042-0_61.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:10Z","timestamp":1605648310000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59042-0_61"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540590422","9783540491750"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-59042-0_61","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}