{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T03:53:46Z","timestamp":1725767626258},"publisher-location":"Boston, MA","reference-count":19,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9781475752755"},{"type":"electronic","value":"9780387356082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/978-0-387-35608-2_21","type":"book-chapter","created":{"date-parts":[[2013,12,29]],"date-time":"2013-12-29T21:57:25Z","timestamp":1388354245000},"page":"243-254","source":"Crossref","is-referenced-by-count":3,"title":["One-Way Permutations and Self-Witnessing Languages"],"prefix":"10.1007","author":[{"given":"Christopher M.","family":"Homan","sequence":"first","affiliation":[]},{"given":"Mayur","family":"Thakur","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","volume-title":"Polynomial Reducibilities and Complete Sets. PhD thesis","author":"L Berman","year":"1977","unstructured":"L. Berman. Polynomial Reducibilities and Complete Sets. PhD thesis, Cornell University, Ithaca, NY, 1977."},{"issue":"4","key":"21_CR2","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T Baker","year":"1975","unstructured":"T. Baker, J. Gill, and R. Solovay. Relativizations of the P=?NP question. SIAM Journal on Computing, 4 (4): 431\u2013442, 1975.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"21_CR3","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 6 (2): 305\u2013322, 1977.","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"21_CR4","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. Book","year":"1974","unstructured":"R. Book. Tally languages and complexity classes. Information and Control, 26 (2): 186\u2013193, 1974.","journal-title":"Information and Control"},{"key":"21_CR5","first-page":"213","volume-title":"Proceedings of the 11th Annual IEEE Conference on Computational Complexity","author":"S Fenner","year":"1996","unstructured":"S. Fenner, L. Fortnow, A. Naik, and J. Rogers. On inverting onto functions. In Proceedings of the 11th Annual IEEE Conference on Computational Complexity, pages 213\u2013222. IEEE Computer Society Press, May 1996."},{"issue":"3","key":"21_CR6","first-page":"299","volume":"1","author":"E Gr\u00e4del","year":"1994","unstructured":"E. Gr\u00e4del. Definability on finite structures and the existence of one-way functions. Methods of Logic in Computer Science, 1 (3): 299\u2013314, 1994.","journal-title":"Methods of Logic in Computer Science"},{"issue":"2","key":"21_CR7","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1137\/0217018","volume":"17","author":"J Grollmann","year":"1988","unstructured":"J. Grollmann and A. Selman. Complexity measures for public-key cryptosystems. SIAM Journal on Computing, 17 (2): 309\u2013335, 1988.","journal-title":"SIAM Journal on Computing"},{"key":"21_CR8","volume-title":"Hemaspaandra","author":"L","year":"2000","unstructured":"L. Hemaspaandra. Personal Communication, October 2000."},{"issue":"13","key":"21_CR9","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/0304-3975(88)90022-9","volume":"58","author":"J Hartmanis","year":"1988","unstructured":"J. Hartmanis and L. Hemachandra. Complexity classes without machines: On complete languages for UP. Theoretical Computer Science, 58 (13): 129\u2013142, 1988.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"21_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1119","volume":"121","author":"L Hemaspaandra","year":"1995","unstructured":"L. Hemaspaandra and S. Jha. Defying upward and downward separation. Information and Computation, 121 (1): 1\u201313, 1995.","journal-title":"Information and Computation"},{"key":"21_CR11","unstructured":"C Homan. Low ambiguity in strong, total, associative, one-way functions. Technical Report TR734, University of Rochester, Computer Science Department, August 2000. Thu, 10 Aug 00 13:36:44 GMT."},{"issue":"1\u20132","key":"21_CR12","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0304-3975(00)00014-1","volume":"244","author":"L. Hemaspaandra","year":"2000","unstructured":"L. Hemaspaandra and J. Rothe. Characterizing the existence of one-way permutations. Theoretical Computer Science, 244 (1\u20132): 257\u2013261, 2000.","journal-title":"Theoretical Computer Science"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"C. Homan and M. Thakur. One-way permutations and self-witnessing languages. Technical Report 760, University of Rochester, 2001.","DOI":"10.1007\/978-0-387-35608-2_21"},{"issue":"1","key":"21_CR14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(85)90085-4","volume":"37","author":"K. Ko","year":"1985","unstructured":"K. Ko. On some natural complete operators. Theoretical Computer Science, 37 (1): 1\u201330, 1985.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"21_CR15","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/S0020-0190(01)00269-1","volume":"82","author":"J Rothe","year":"2002","unstructured":"J. Rothe and L. Hemaspaandra. On characterizing the existence of partial one-way permutations. Information Processing Letters, 82 (3): 165\u2013171, 2002.","journal-title":"Information Processing Letters"},{"issue":"12","key":"21_CR16","first-page":"89","volume":"74","author":"R Rao","year":"2000","unstructured":"R. Rao, J. Rothe, and O. Watanabe. Upward separation for FewP and related classes. Information Processing Letters, 52 (4): 175\u2013180, 1994. Corrigendum appears in same journal, Volume 74, number 1\u20132, page 89, 2000.","journal-title":"Upward separation for FewP and related classes. Information Processing Letters, 52 (4): 175-180, 1994. Corrigendum appears in same journal"},{"issue":"3","key":"21_CR17","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01374525","volume":"25","author":"A Selman","year":"1992","unstructured":"A. Selman. A survey of one-way functions in complexity theory. Mathematical Systems Theory, 25 (3): 203\u2013221, 1992.","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"21_CR18","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. The relative complexity of checking and evaluating. Information Processing Letters, 5 (1): 20\u201323, 1976.","journal-title":"Information Processing Letters"},{"issue":"3","key":"21_CR19","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/0020-0190(88)90071-3","volume":"27","author":"O Watanabe","year":"1988","unstructured":"O. Watanabe. On hardness of one-way functions. Information Processing Letters, 27 (3): 151\u2013157, 1988.","journal-title":"Information Processing Letters"}],"container-title":["Foundations of Information Technology in the Era of Network and Mobile Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-35608-2_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T00:36:51Z","timestamp":1557794211000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-0-387-35608-2_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9781475752755","9780387356082"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-35608-2_21","relation":{},"subject":[],"published":{"date-parts":[[2002]]}}}