{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T05:35:45Z","timestamp":1648618545860},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2011,10,8]],"date-time":"2011-10-08T00:00:00Z","timestamp":1318032000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2012,8]]},"DOI":"10.1007\/s00224-011-9365-0","type":"journal-article","created":{"date-parts":[[2011,10,7]],"date-time":"2011-10-07T06:03:13Z","timestamp":1317967393000},"page":"248-265","source":"Crossref","is-referenced-by-count":1,"title":["Collapsing and Separating Completeness Notions Under Average-Case and Worst-Case Hypotheses"],"prefix":"10.1007","volume":"51","author":[{"given":"Xiaoyang","family":"Gu","sequence":"first","affiliation":[]},{"given":"John M.","family":"Hitchcock","sequence":"additional","affiliation":[]},{"given":"A.","family":"Pavan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,10,8]]},"reference":[{"key":"9365_CR1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S. Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"9365_CR2","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/S0890-5401(03)00091-9","volume":"186","author":"A. Amir","year":"2003","unstructured":"Amir, A., Beigel, R., Gasarch, W.: Some connections between bounded query classes and non-uniform complexity. Inf. Comput. 186, 104\u2013139 (2003)","journal-title":"Inf. Comput."},{"key":"9365_CR3","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1109\/CCC.2002.1004349","volume-title":"Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity","author":"M. Agrawal","year":"2002","unstructured":"Agrawal, M.: Pseudo-random generators and structure of complete degrees. In: Proceedings of the Seventeenth Annual IEEE Conference on Computational Complexity, pp. 139\u2013147 (2002)"},{"issue":"3","key":"9365_CR4","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1006\/jcss.1999.1674","volume":"61","author":"K. Ambos-Spies","year":"2000","unstructured":"Ambos-Spies, K., Bentzien, L.: Separating NP-completeness notions under strong hypotheses. J.\u00a0Comput. Syst. Sci. 61(3), 335\u2013361 (2000)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9365_CR5","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Watanabe, O.: One-way functions and the isomorphism conjecture. Technical report TR09-019, Electronic Colloquium on Computational Complexity, 2009","DOI":"10.1109\/CCC.2009.17"},{"key":"9365_CR6","unstructured":"Beigel, R.: Query-limited reducibilities. PhD thesis, Stanford University, 1987"},{"key":"9365_CR7","unstructured":"Berman, L.: Polynomial reducibilities and complete sets. PhD thesis, Cornell University, 1977"},{"issue":"1","key":"9365_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01276436","volume":"2","author":"R. Beigel","year":"1992","unstructured":"Beigel, R., Feigenbaum, J.: On being incoherent without being very hard. Comput. Complex. 2(1), 1\u201317 (1992)","journal-title":"Comput. Complex."},{"key":"9365_CR9","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless EXPTIME has publishable proofs. Comput. Complex. 3, 307\u2013318 (1993)","journal-title":"Comput. Complex."},{"key":"9365_CR10","first-page":"2","volume-title":"IEEE Conference on Computational Complexity","author":"H. Buhrman","year":"1997","unstructured":"Buhrman, H., Fortnow, L., Torenvliet, L.: Six hypotheses in search of a theorem. In: IEEE Conference on Computational Complexity, pp. 2\u201312 (1997)"},{"key":"9365_CR11","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"Berman, L., Hartmanis, J.: On isomorphism and density of NP and other complete sets. SIAM J. Comput. 6, 305\u2013322 (1977)","journal-title":"SIAM J. Comput."},{"key":"9365_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/CCC.2008.21","volume-title":"Proceedings of the 23rd Annual IEEE Conference on Computational Complexity","author":"H. Buhrman","year":"2008","unstructured":"Buhrman, H., Hitchcock, J.M.: NP-hard sets are exponentially dense unless NP\u2286coNP\/poly. In: Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, pp. 1\u20137. IEEE Comput. Soc., Los Alamitos (2008)"},{"issue":"2","key":"9365_CR13","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s00224-008-9163-5","volume":"47","author":"H. Buhrman","year":"2010","unstructured":"Buhrman, H., Hescott, B., Homer, S., Torenvliet, L.: Non-uniform reductions. Theory Comput. Syst. 47(2), 317\u2013341 (2010)","journal-title":"Theory Comput. Syst."},{"key":"9365_CR14","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/BF02090397","volume":"24","author":"H. Buhrman","year":"1991","unstructured":"Buhrman, H., Homer, S., Torenvliet, L.: Completeness for nondeterministic complexity classes. Math. Syst. Theory 24, 179\u2013200 (1991)","journal-title":"Math. Syst. Theory"},{"key":"9365_CR15","first-page":"151","volume-title":"Proceedings of the Third ACM Symposium on the Theory of Computing","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the Third ACM Symposium on the Theory of Computing, pp. 151\u2013158 (1971)"},{"key":"9365_CR16","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/s000370050009","volume":"7","author":"J. Feigenbaum","year":"1998","unstructured":"Feigenbaum, J., Fortnow, L., Laplante, S., Naik, A.: On coherence, random-self-reducibility, and self-correction. Comput. Complex. 7, 174\u2013191 (1998)","journal-title":"Comput. Complex."},{"key":"9365_CR17","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1007\/BF01202287","volume":"4","author":"J. Feigenbaum","year":"1994","unstructured":"Feigenbaum, J., Fortnow, L., Lund, C., Spielman, D.: The power of adaptiveness and additional queries in random-self-reductions. Comput. Complex. 4, 158\u2013174 (1994)","journal-title":"Comput. Complex."},{"key":"9365_CR18","first-page":"133","volume-title":"Proceedings of the 40th Annual ACM Symposium on Theory of Computing","author":"L. Fortnow","year":"2008","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pp. 133\u2013142 (2008)"},{"issue":"4","key":"9365_CR19","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1137\/0221044","volume":"21","author":"K. Ganesan","year":"1992","unstructured":"Ganesan, K., Homer, S.: Complete problems and strong polynomial reducibilities. SIAM J. Comput. 21(4), 733\u2013742 (1992)","journal-title":"SIAM J. Comput."},{"key":"9365_CR20","first-page":"25","volume-title":"Proceedings of the Twenty-First ACM Symposium on the Theory of Computing","author":"O. Goldreich","year":"1989","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First ACM Symposium on the Theory of Computing, pp. 25\u201332 (1989)"},{"key":"9365_CR21","unstructured":"Goldreich, O., Levin, L., Nisan, N.: On constructing 1-1 one-way function. Technical report TR95-029, ECCC, 1995"},{"issue":"2","key":"9365_CR22","doi-asserted-by":"crossref","first-page":"194","DOI":"10.1006\/jcss.1996.0061","volume":"53","author":"E. Hemaspaandra","year":"1996","unstructured":"Hemaspaandra, E., Naik, A., Ogiwara, M., Selman, A.: P-selective sets and reducing search to decision vs. self-reducibility. J. Comput. Syst. Sci. 53(2), 194\u2013209 (1996)","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"9365_CR23","doi-asserted-by":"crossref","first-page":"694","DOI":"10.1016\/j.ic.2006.10.005","volume":"205","author":"J.M. Hitchcock","year":"2007","unstructured":"Hitchcock, J.M., Pavan, A.: Comparing reductions to NP-complete sets. Inf. Comput. 205(5), 694\u2013706 (2007)","journal-title":"Inf. Comput."},{"issue":"2","key":"9365_CR24","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1007\/s00224-007-9000-2","volume":"42","author":"J.M. Hitchcock","year":"2008","unstructured":"Hitchcock, J.M., Pavan, A., Vinodchandran, N.V.: Partial Bi-immunity, scaled dimension, and NP-completeness. Theory Comput. Syst. 42(2), 131\u2013142 (2008)","journal-title":"Theory Comput. Syst."},{"key":"9365_CR25","first-page":"538","volume-title":"Proceedings of the 36th Annual Conference on Foundations of Computer Science","author":"R. Impagliazzo","year":"1995","unstructured":"Impagliazzo, R.: Hard-core distributions for somewhat hard problems. In: Proceedings of the 36th Annual Conference on Foundations of Computer Science, pp. 538\u2013545 (1995)"},{"key":"9365_CR26","first-page":"220","volume-title":"Proceedings of the 29th Symposium on Theory of Computing","author":"R. Impagliazzo","year":"1997","unstructured":"Impagliazzo, R., Wigderson, A.: P=BPP if E requires exponential circuits: derandomizing the XOR lemma. In: Proceedings of the 29th Symposium on Theory of Computing, pp. 220\u2013229 (1997)"},{"issue":"3","key":"9365_CR27","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1109\/TIT.1962.1057714","volume":"8","author":"S. Johnson","year":"1962","unstructured":"Johnson, S.: A new upper bound for error correcting codes. IRE Trans. Inf. Theory 8(3), 203\u2013207 (1962)","journal-title":"IRE Trans. Inf. Theory"},{"key":"9365_CR28","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin, L.: Universal sorting problems. Probl. Inf. Transm. 9, 265\u2013266 (1973). English translation of original in Problemy Peredaci Informacii","journal-title":"Probl. Inf. Transm."},{"key":"9365_CR29","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0304-3975(75)90016-X","volume":"1","author":"R. Ladner","year":"1975","unstructured":"Ladner, R., Lynch, N., Selman, A.: A comparison of polynomial time reducibilities. Theor. Comput. Sci. 1, 103\u2013123 (1975)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9365_CR30","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1137\/S0097539792237498","volume":"23","author":"J.H. Lutz","year":"1994","unstructured":"Lutz, J.H., Mayordomo, E.: Measure, stochasticity, and the density of hard languages. SIAM J. Comput. 23(4), 762\u2013779 (1994)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"9365_CR31","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"J.H. Lutz","year":"1996","unstructured":"Lutz, J.H., Mayordomo, E.: Cook versus Karp-Levin: separating completeness notions if NP is not small. Theor. Comput. Sci. 164(1\u20132), 141\u2013163 (1996)","journal-title":"Theor. Comput. Sci."},{"key":"9365_CR32","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs randomness. J. Comput. Syst. Sci. 49, 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9365_CR33","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/882116.882125","volume":"34","author":"A. Pavan","year":"2003","unstructured":"Pavan, A.: Comparison of reductions and completeness notions. SIGACT News 34(2), 27\u201341 (2003)","journal-title":"SIGACT News"},{"issue":"3","key":"9365_CR34","doi-asserted-by":"crossref","first-page":"906","DOI":"10.1137\/S0097539701387039","volume":"31","author":"A. Pavan","year":"2002","unstructured":"Pavan, A., Selman, A.: Separation of NP-completeness notions. SIAM J. Comput. 31(3), 906\u2013918 (2002)","journal-title":"SIAM J. Comput."},{"key":"9365_CR35","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.ic.2003.05.001","volume":"188","author":"A. Pavan","year":"2004","unstructured":"Pavan, A., Selman, A.: Bi-immunity separates strong NP-completeness notions. Inf. Comput. 188, 116\u2013126 (2004)","journal-title":"Inf. Comput."},{"issue":"2","key":"9365_CR36","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","volume":"62","author":"M. Sudan","year":"2001","unstructured":"Sudan, M., Trevisan, L., Vadhan, S.: Pseudorandom generators without the XOR lemma. J.\u00a0Comput. Syst. Sci. 62(2), 236\u2013266 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9365_CR37","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/0304-3975(87)90132-0","volume":"54","author":"O. Watanabe","year":"1987","unstructured":"Watanabe, O.: A comparison of polynomial time completeness notions. Theor. Comput. Sci. 54, 249\u2013265 (1987)","journal-title":"Theor. Comput. Sci."},{"key":"9365_CR38","first-page":"80","volume-title":"Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science","author":"A. Yao","year":"1982","unstructured":"Yao, A.: Theory and applications of trapdoor functions. In: Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science, pp. 80\u201391 (1982)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9365-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-011-9365-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-011-9365-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,17]],"date-time":"2019-06-17T05:03:47Z","timestamp":1560747827000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-011-9365-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,8]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,8]]}},"alternative-id":["9365"],"URL":"https:\/\/doi.org\/10.1007\/s00224-011-9365-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,8]]}}}