{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T18:42:48Z","timestamp":1794336168290,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540281931","type":"print"},{"value":"9783540318736","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11537311_37","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T10:00:06Z","timestamp":1127815206000},"page":"422-432","source":"Crossref","is-referenced-by-count":0,"title":["Relations Between Average-Case and Worst-Case Complexity"],"prefix":"10.1007","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"2","key":"37_CR1","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1006\/jcss.2002.1835","volume":"65","author":"V. Arvind","year":"2002","unstructured":"Arvind, V., K\u00f6bler, J.: New lowness results for ZPPNP. Journal of Computer and System Sciences\u00a065(2), 257\u2013277 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR2","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: Proc. 17th Annual ACM Symp. on Theory of Computing, pp. 421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"issue":"2","key":"37_CR3","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0022-0000(92)90019-F","volume":"44","author":"S. Ben-David","year":"1992","unstructured":"Ben-David, S., Chor, B., Goldreich, O., Luby, M.: On the theory of average case complexity. Journal of Computer and System Sciences\u00a044(2), 193\u2013219 (1992)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97062-7","volume-title":"Structural Complexity I","author":"J. Balc\u00e1zar","year":"1988","unstructured":"Balc\u00e1zar, J., Diaz, J., Gabarr\u00f3, J.: Structural Complexity I. Springer, Berlin (1988)"},{"key":"37_CR5","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Nisan, N., Wigderson, A.: BPP has subexponential time simulations unless exptime has publishable proofs. In: Proceedings of the 6th Annual Conference on Structure in Complexity Theory, 1991, pp. 213\u2013219 (1991)","DOI":"10.1109\/SCT.1991.160263"},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1007\/3-540-36494-3_20","volume-title":"Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science","author":"H. Buhrman","year":"2003","unstructured":"Buhrman, H., Fortnow, L., Pavan, A.: Some results on derandomization. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 212\u2013222. Springer, Heidelberg (2003)"},{"issue":"2","key":"37_CR7","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L. Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-merlin games: a randomized proof system, and a hierarchy of complexity class. Journal of Computer and System Sciences\u00a036(2), 254\u2013276 (1988)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR8","unstructured":"Buhrman, H.: Resource bounded reductions. PhD thesis, University of Amsterdam (1993)"},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Feige, U., Lund, C.: On the hardness of computing permanent of random matrices. In: Proceedings of 24th Annual ACM Symposium on Theory of Computing, pp. 643\u2013654 (1992)","DOI":"10.1145\/129712.129775"},{"key":"37_CR10","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(92)90195-2","volume":"43","author":"P. Gemmel","year":"1992","unstructured":"Gemmel, P., Sudan, M.: Higly resilient correctors for polynomials. Information Processing Letters\u00a043, 169\u2013174 (1992)","journal-title":"Information Processing Letters"},{"key":"37_CR11","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/s00037-003-0178-7","volume":"12","author":"D. Gutfreund","year":"2003","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: Uniform hardness vs. randomness tradeoffs for Arth ur-Merlin games. Computational Complexity\u00a012, 85\u2013130 (2003)","journal-title":"Computational Complexity"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Gurevich, Y.: Average case completeness. Journal of Computer and System Sciences\u00a042, 346\u2013398 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"37_CR13","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1109\/SCT.1995.514853","volume-title":"Proceedings of the 10th Annual Conference on Structure in Complexity Theory","author":"R. Impagliazzo","year":"1995","unstructured":"Impagliazzo, R.: A personal view of average-case complexity theory. In: Proceedings of the 10th Annual Conference on Structure in Complexity Theory, pp. 134\u2013147. IEEE Computer Society Press, Los Alamitos (1995)"},{"key":"37_CR14","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp. 220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"1","key":"37_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.ic.2003.05.002","volume":"190","author":"J. K\u00f6bler","year":"2004","unstructured":"K\u00f6bler, J., Schuler, R.: Average-case intractability vs. worst-case intractability. Information and Computation\u00a0190(1), 1\u201317 (2004)","journal-title":"Information and Computation"},{"key":"37_CR16","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"A. Klivans","year":"2002","unstructured":"Klivans, A., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing\u00a031, 1501\u20131526 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"37_CR17","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"Levin, L.: Average case complete problems. SIAM Journal of Computing\u00a015, 285\u2013286 (1986)","journal-title":"SIAM Journal of Computing"},{"key":"37_CR18","doi-asserted-by":"crossref","unstructured":"Lipton, R.: New directions in testing. In: Distributed Computing and Cryptography. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 2, pp. 191\u2013202. American Mathematics Society (1991)","DOI":"10.1090\/dimacs\/002\/13"},{"key":"37_CR19","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"37_CR20","doi-asserted-by":"crossref","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudo-random generator. In: 42nd IEEE Symposium on Foundations of Computer Science, pp. 648\u2013657 (2001)","DOI":"10.1109\/SFCS.2001.959941"},{"key":"37_CR21","unstructured":"Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. Technical Report TR 04-086, ECCC (2004)"},{"key":"37_CR22","doi-asserted-by":"crossref","unstructured":"Valiant, L., Vazirani, V.: NP is as easy as detecting unique solutions. In: Proc. 17th ACM Symp. Theory of Computing, pp. 458\u2013463 (1985)","DOI":"10.1145\/22145.22196"},{"key":"37_CR23","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0304-3975(83)90015-4","volume":"26","author":"S. \u017d\u00e1k","year":"1983","unstructured":"\u017d\u00e1k, S.: A Turing machine time hierarchy. Theor. Computer Science\u00a026, 327\u2013333 (1983)","journal-title":"Theor. Computer Science"},{"key":"37_CR24","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/978-1-4612-1872-2_12","volume-title":"Complexity Theory Retrospective II","author":"J. Wang","year":"1997","unstructured":"Wang, J.: Average-case computational complexity theory. In: Hemaspaandra, L., Selman, A. (eds.) Complexity Theory Retrospective II, pp. 295\u2013328. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11537311_37.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T15:12:25Z","timestamp":1605625945000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11537311_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281931","9783540318736"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/11537311_37","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/11537311","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}