{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T16:43:58Z","timestamp":1787503438448,"version":"build-2736575974"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540164869","type":"print"},{"value":"9783540398257","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16486-3_89","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T13:46:28Z","timestamp":1330177588000},"page":"51-65","source":"Crossref","is-referenced-by-count":8,"title":["One-way functions and circuit complexity"],"prefix":"10.1007","author":[{"given":"R. B.","family":"Boppana","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J. C.","family":"Lagarias","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"L. Adleman and K. Manders, \u201cReducibility, randomness, and intractibility,\u201d Proceedings of 9th ACM Symposium on Theory of Computing, 1977, pp. 151\u2013163.","DOI":"10.1145\/800105.803405"},{"key":"5_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0168-0072(83)90038-6","volume":"24","author":"M. Ajtai","year":"1983","unstructured":"M. Ajtai, \u201c\u03a3 1 1 -formulae on finite structures,\u201d Annals of Pure and Applied Logic 24, 1983, pp. 1\u201348.","journal-title":"Annals of Pure and Applied Logic"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"M. Ajtai and A. Wigderson, \u201cDeterministic simulation of probabilistic constant depth circuits,\u201d Proceedings of 26th IEEE Symposium on Foundations of Computer Science, 1985, pp. 11\u201319.","DOI":"10.1109\/SFCS.1985.19"},{"key":"5_CR4","unstructured":"D. Barrington, personal communication, December 1985."},{"key":"5_CR5","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 SIAM Journal on Computing 13, 1984, pp. 850\u2013864.","journal-title":"SIAM Journal on Computing"},{"key":"5_CR6","doi-asserted-by":"crossref","first-page":"877","DOI":"10.1109\/TIT.1983.1056754","volume":"29","author":"G. Brassard","year":"1983","unstructured":"G. Brassard, \u201cRelativized cryptography,\u201d IEEE Transactions on Information Theory 29, 1983, pp. 877\u2013894.","journal-title":"IEEE Transactions on Information Theory"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, L. Stockmeyer and U. Vishkin, \u201cA complexity theory for unbounded fan-in parallelism,\u201d Proceedings of 23rd IEEE Symposium on Foundations of Computer Science, 1982, pp. 1\u201313.","DOI":"10.1109\/SFCS.1982.3"},{"key":"5_CR8","doi-asserted-by":"crossref","unstructured":"S. A. Cook, \u201cThe complexity of theorem proving procedures,\u201d Proceedings of 3rd ACM Symposium on Theory of Computing, 1971, pp. 151\u2013158.","DOI":"10.1145\/800157.805047"},{"key":"5_CR9","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. B. Saxe and M. Sipser, \u201cParity, circuits, and the polynomial time hierarchy,\u201d Mathematical Systems Theory 17, 1984, pp. 13\u201328.","journal-title":"Mathematical Systems Theory"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"J. Grollman and A. L. Selman, \u201cComplexity measures for public-key cryptosystems,\u201d Proceedings of 25th IEEE Symposium on Foundations of Computer Science, 1984, pp. 495\u2013503.","DOI":"10.1109\/SFCS.1984.715952"},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"J. Hastad, \u201cImproved lower bounds for small depth circuits,\u201d to appear in Proceedings of 18th ACM Symposium on Theory of Computing, 1986.","DOI":"10.1145\/12130.12132"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"J. Hastad, \u201cOne-way permutations in NC 0,\u201d preprint, February 1986.","DOI":"10.1016\/0020-0190(87)90053-6"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"N. Immerman, \u201cLanguages which capture complexity classes,\u201d Proceedings of 15th ACM Symposium on Theory of Computing, 1983, pp. 347\u2013354.","DOI":"10.1145\/800061.808765"},{"key":"5_CR14","first-page":"191","volume":"28","author":"R. M. Karp","year":"1982","unstructured":"R. M. Karp and R. J. Lipton, \u201cTuring machines that take advice,\u201d L'Enseignment Mathematique 28, 1982, pp. 191\u2013209. (preliminary version appeared in \u201cSome connections between non-uniform and uniform complexity classes,\u201d Proceedings of 12th ACM Symposium on Theory of Computing, 1980, pp. 302\u2013309.)","journal-title":"L'Enseignment Mathematique"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"L. A. Levin, \u201cOne-way functions and pseudorandom generators,\u201d Proceedings of 17th ACM Symposium on Theory of Computing, 1985, pp. 363\u2013365.","DOI":"10.1145\/22145.22185"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"T. J. Long, \u201cOn \u03b3-reducibility versus polynomial time many-one reducibility,\u201d Proceedings of 11th ACM Symposium on Theory of Computing, 1979, pp. 278\u2013287.","DOI":"10.1145\/800135.804421"},{"key":"5_CR17","unstructured":"A. Odlyzko, \u201cDiscrete logarithms in finite fields and their cryptographic significance,\u201d preprint."},{"key":"5_CR18","volume-title":"The Complexity of Computing","author":"J. E. Savage","year":"1976","unstructured":"J. E. Savage, The Complexity of Computing, John Wiley and Sons, New York, NY, 1976."},{"key":"5_CR19","unstructured":"A. Selman, \u201cRemarks about natural self-reducible sets in NP and complexity measures for public key cryptosystems,\u201d preprint."},{"key":"5_CR20","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1016\/0020-0190(76)90097-1","volume":"5","author":"L. Valiant","year":"1976","unstructured":"L. Valiant, \u201cRelative complexity of checking and evaluating,\u201d Information Processing Letters 5, 1976, pp. 20\u201323.","journal-title":"Information Processing Letters"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"A. C. Yao, \u201cTheory and applications of trapdoor functions,\u201d Proceedings of 23rd IEEE Symposium on Foundations of Computer Science, 1982, pp. 80\u201391.","DOI":"10.1109\/SFCS.1982.45"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"A. C. Yao, \u201cSeparating the polynomial-time hierarchy by oracles,\u201d Proceedings of 26th IEEE Symposium on Foundations of Computer Science, 1985, pp. 1\u201310.","DOI":"10.1109\/SFCS.1985.49"}],"container-title":["Lecture Notes in Computer Science","Structure in Complexity Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16486-3_89.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:10:32Z","timestamp":1605625832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16486-3_89"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540164869","9783540398257"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-16486-3_89","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986]]}}}