{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T16:48:19Z","timestamp":1725468499442},"publisher-location":"Berlin, Heidelberg","reference-count":39,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055799","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T17:36:31Z","timestamp":1155836191000},"page":"493-502","source":"Crossref","is-referenced-by-count":3,"title":["Average-case intractability vs. worst-case intractability"],"prefix":"10.1007","author":[{"given":"Johannes","family":"K\u00f6bler","sequence":"first","affiliation":[]},{"given":"Rainer","family":"Schuler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"46_CR1","doi-asserted-by":"crossref","unstructured":"V. Arvind and J. K\u00f6bler. On resource-bounded measure and pseudorandomness. In Proc. 17th Conference on Foundations of Software Technology and Theoretical Computer Science, volume 1346 of Lecture Notes in Computer Science, pages 235\u2013249. Springer-Verlag, 1997.","DOI":"10.1007\/BFb0058034"},{"issue":"1","key":"46_CR2","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01201814","volume":"29","author":"V. Arvind","year":"1996","unstructured":"V. Arvind, J. K\u00f6bler, and M. Mundhenk. Upper bounds for the complexity of sparse and tally descriptions. Mathematical Systems Theory, 29(1):63\u201394, 1996.","journal-title":"Mathematical Systems Theory"},{"issue":"2","key":"46_CR3","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1142\/S012905419500010X","volume":"6","author":"V. Arvind","year":"1995","unstructured":"V. Arvind, J. K\u00f6bler, and R. Schuler. On helping and interactive proof systems. International Journal of Foundations of Computer Science, 6(2):137\u2013153, 1995.","journal-title":"International Journal of Foundations of Computer Science"},{"key":"46_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01200055","volume":"1","author":"L. Babai","year":"1991","unstructured":"L. Babai, L. Fortnow, and C. Lund. Non-deterministic exponential time has twoprover interactive protocols. Computational Complexity, 1:1\u201340, 1991.","journal-title":"Computational Complexity"},{"key":"46_CR5","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/BF01275486","volume":"3","author":"L. Babai","year":"1993","unstructured":"L. Babai, L. Fortnow, N. Nisan, and A. Wigderson. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity, 3:307\u2013318, 1993.","journal-title":"Computational Complexity"},{"key":"46_CR6","doi-asserted-by":"crossref","unstructured":"J. L. Balc\u00e1zar, J. D\u00edaz, and J. Gabarr\u00f3. Structural Complexity I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, second edition, 1995.","DOI":"10.1007\/978-3-642-79235-9"},{"key":"46_CR7","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1016\/0304-3975(92)90353-H","volume":"99","author":"J.L Balc\u00e1zar","year":"1992","unstructured":"J.L Balc\u00e1zar and U. Sch\u00f6ning. Logarithmic advice classes. Theoretical Computer Science, 99:279\u2013290, 1992.","journal-title":"Theoretical Computer Science"},{"key":"46_CR8","doi-asserted-by":"crossref","unstructured":"D. Beaver and J. Feigenbaum. Hiding instances in multioracle queries. In Proc. 7th Symposium on Theoretical Aspects of Computer Science, volume 415 of Lecture Notes in Computer Science, pages 37\u201348. Springer-Verlag, 1990.","DOI":"10.1007\/3-540-52282-4_30"},{"key":"46_CR9","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(92)90084-S","volume":"103","author":"R. Beigel","year":"1992","unstructured":"R. Beigel and J. Gill. Counting classes: thresholds, parity, mods, and fewness. Theoretical Computer Science, 103:3\u201323, 1992.","journal-title":"Theoretical Computer Science"},{"key":"46_CR10","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity. Journal of Computer and System Sciences, 44:193\u2013219, 1992.","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR11","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1006\/jcss.1996.0032","volume":"52","author":"N. Bshouty","year":"1996","unstructured":"N. Bshouty, R. Cleve, R. Gavald\u00e0, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52:421\u2013433, 1996.","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/BF02090768","volume":"23","author":"J. Cai","year":"1990","unstructured":"J. Cai and L. A. Hemachandra. On the power of parity polynomial time. Mathematical Systems Theory, 23:95\u2013106, 1990.","journal-title":"Mathematical Systems Theory"},{"key":"46_CR13","doi-asserted-by":"crossref","unstructured":"J.-Y. Cai and A. Selman. Fine separation of average time complexity classes. In Proc. 13th Symposium on Theoretical Aspects of Computer Science, volume 1046 of Lecture Notes in Computer Science, pages 331\u2013343. Springer-Verlag, 1996.","DOI":"10.1007\/3-540-60922-9_28"},{"key":"46_CR14","doi-asserted-by":"publisher","first-page":"994","DOI":"10.1137\/0222061","volume":"22","author":"J. Feigenbaum","year":"1993","unstructured":"J. Feigenbaum and L. Fortnow. Random-self-reducibility of complete sets. SIAM Journal on Computing, 22:994\u20131005, 1993.","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"46_CR15","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1006\/jcss.1995.1037","volume":"50","author":"R. Gavald\u00e0","year":"1995","unstructured":"R. Gavald\u00e0. Bounding the complexity of advice functions. Journal of Computer and System Sciences, 50(3):468\u2013475, 1995.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"46_CR16","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1006\/jcss.1995.1036","volume":"50","author":"F. Green","year":"1995","unstructured":"F. Green, J. K\u00f6bler, K. Regan, T. Schwentick, and J. Tor\u00e1n. The power of the middle bit of a #P function. Journal of Computer and System Sciences, 50(3):456\u2013467, 1995.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"46_CR17","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich. Average case completeness. Journal of Computer and System Sciences, 42(3):346\u2013398, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR18","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(90)90081-R","volume":"74","author":"U. Hertrampf","year":"1990","unstructured":"U. Hertrampf. Relations among MOD-classes. Theoretical Computer Science, 74:325\u2013328, 1990.","journal-title":"Theoretical Computer Science"},{"key":"46_CR19","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo. A personal view of average-case complexity. In Proc. 10th Structure in Complexity Theory Conference, pages 134\u2013147. IEEE Computer Society Press, 1995.","DOI":"10.1109\/SCT.1995.514853"},{"key":"46_CR20","doi-asserted-by":"crossref","unstructured":"R. M. Karp and R. J. Lipton. Some connections between nonuniform and uniform complexity classes. In Proc. 12th ACM Symposium on Theory of Computing, pages 302\u2013309. ACM Press, 1980.","DOI":"10.1145\/800141.804678"},{"issue":"2","key":"46_CR21","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0304-3975(94)00016-6","volume":"134","author":"J. K\u00f6bler","year":"1994","unstructured":"J. K\u00f6bler. Locating P\/poly optimally in the extended low hierarchy. Theoretical Computer Science, 134(2):263\u2013285, 1994.","journal-title":"Theoretical Computer Science"},{"key":"46_CR22","unstructured":"J. K\u00f6bler and R. Schuler. Average-case intractability vs. worst-case intractability. See ftp:\/\/theorie.informatik.uni-ulm.de\/pub\/papers\/ti\/ap.ps.gz."},{"issue":"1","key":"46_CR23","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF01201812","volume":"29","author":"J. K\u00f6bler","year":"1996","unstructured":"J. K\u00f6bler and S. Toda. On the power of generalized MOD-classes. Mathematical Systems Theory, 29(1):33\u201346, 1996.","journal-title":"Mathematical Systems Theory"},{"key":"46_CR24","doi-asserted-by":"crossref","unstructured":"J. K\u00f6bler and O. Watanabe. New collapse consequences of NP having small circuits. In Proc. 22nd International Colloquium on Automata, Languages, and Programming, volume 944 of Lecture Notes in Computer Science, pages 196\u2013207. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60084-1_74"},{"key":"46_CR25","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"L. Levin. Average case complete problems. SIAM Journal on Computing, 15:285\u2013286, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"46_CR26","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(92)90138-L","volume":"42","author":"M. Li","year":"1992","unstructured":"M. Li and P.M.B. Vit\u00e1nyi. Average case complexity under the universal distribution equals worst-case complexity. Information Processing Letters, 42:145\u2013149, 1992.","journal-title":"Information Processing Letters"},{"key":"46_CR27","doi-asserted-by":"crossref","unstructured":"R. J. Lipton. New directions in testing. In J. Feigenbaum and M. Merritt, editors, Distributed Computing and Cryptography, volume 2 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1991.","DOI":"10.1090\/dimacs\/002\/13"},{"key":"46_CR28","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s002240000060","volume":"30","author":"J. H. Lutz","year":"1997","unstructured":"J. H. Lutz. Observations on measure and lowness for \u03b4 2 P . Theory of Computing Systems, 30:429\u2013442, 1997.","journal-title":"Theory of Computing Systems"},{"key":"46_CR29","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. The quantitative structure of exponential time. In L. A. Hemaspaandra and A. L. Selman, editors, Complexity Theory Retrospective II, pages 225\u2013260. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"46_CR30","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/0304-3975(95)00189-1","volume":"164","author":"J. H. Lutz","year":"1996","unstructured":"J. H. Lutz and E. Mayordomo. Cook versus Karp-Levin: separating reducibilities if NP is not small. Theoretical Computer Science, 164:141\u2013163, 1996.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"46_CR31","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1137\/0222012","volume":"22","author":"P.B. Milterson","year":"1993","unstructured":"P.B. Milterson. The complexity of malign measures. SIAM Journal on Computing, 22(1):147\u2013156, 1993.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"46_CR32","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/174644.174648","volume":"41","author":"P. Orponen","year":"1994","unstructured":"P. Orponen, K. Ko, U. Sch\u00f6ning, and O. Watanabe. Instance complexity. Journal of the ACM, 41(1):96\u2013121, 1994.","journal-title":"Journal of the ACM"},{"key":"46_CR33","doi-asserted-by":"crossref","unstructured":"R. E. Schapire. The emerging theory of average-case complexity. Technical Report TM-431, Massachusetts Institut of Technology, 1990.","DOI":"10.21236\/ADA222821"},{"key":"46_CR34","doi-asserted-by":"crossref","unstructured":"U. Sch\u00f6ning. Complexity and Structure, volume 211 of Lecture Notes in Computer Science. Springer-Verlag, 1986.","DOI":"10.1007\/3-540-16079-5"},{"key":"46_CR35","doi-asserted-by":"crossref","unstructured":"R. Schuler. Truth-table closure and Turing closure of average polynomial time have different measures in EXP. In Proc. 11th Annual IEEE Conference on Computational Complexity, pages 190\u2013197. IEEE Computer Society Press, 1996.","DOI":"10.1109\/CCC.1996.507681"},{"key":"46_CR36","doi-asserted-by":"crossref","unstructured":"R. Schuler and O. Watanabe. Towards average-case complexity analysis of NP optimization problems. In Proc. 10th Structure in Complexity Theory Conference, pages 148\u2013159. IEEE Computer Society Press, 1995.","DOI":"10.1109\/SCT.1995.514854"},{"key":"46_CR37","doi-asserted-by":"crossref","unstructured":"R. Schuler and T. Yamakami. Sets computable in polynomial time on average. In Proc. 1st International Computing and Combinatorics Conference, volume 959 of Lecture Notes in Computer Science, pages 400\u2013409. Springer-Verlag, 1995.","DOI":"10.1007\/BFb0030859"},{"key":"46_CR38","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1006\/jcss.1996.0024","volume":"52","author":"R. Schuler","year":"1996","unstructured":"R. Schuler and T. Yamakami. Structural average case complexity. Journal of Computer and System Sciences, 52:308\u2013327, 1996.","journal-title":"Journal of Computer and System Sciences"},{"key":"46_CR39","unstructured":"O. Watanabe, 1996. Personal communication."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055799","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,20]],"date-time":"2019-04-20T18:44:32Z","timestamp":1555785872000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055799"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/bfb0055799","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}