{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T11:23:23Z","timestamp":1649157803280},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T00:00:00Z","timestamp":1194912000000},"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":[[2008,5]]},"DOI":"10.1007\/s00224-007-9071-0","type":"journal-article","created":{"date-parts":[[2007,11,12]],"date-time":"2007-11-12T11:08:13Z","timestamp":1194865693000},"page":"596-607","source":"Crossref","is-referenced-by-count":0,"title":["Relations between Average-Case and Worst-Case Complexity"],"prefix":"10.1007","volume":"42","author":[{"given":"A.","family":"Pavan","sequence":"first","affiliation":[]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,11,13]]},"reference":[{"issue":"2","key":"9071_CR1","doi-asserted-by":"crossref","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 and other complexity classes. J.\u00a0Comput. Syst. Sci. 65(2), 257\u2013277 (2002)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9071_CR2","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: Proc. 17th Annual ACM Symp. on Theory of Computing, pp.\u00a0421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"issue":"2","key":"9071_CR3","doi-asserted-by":"crossref","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. J.\u00a0Comput. System Sci. 36(2), 254\u2013276 (1988)","journal-title":"J.\u00a0Comput. System Sci."},{"key":"9071_CR4","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, pp.\u00a0213\u2013219 (1991)","DOI":"10.1109\/SCT.1991.160263"},{"key":"9071_CR5","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)"},{"issue":"2","key":"9071_CR6","doi-asserted-by":"crossref","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. J.\u00a0Comput. Syst. Sci. 44(2), 193\u2013219 (1992)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9071_CR7","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(74)90473-2","volume":"26","author":"R. Book","year":"1974","unstructured":"Book, R.: Tally languages and complexity classes. Inf. Control 26, 186\u2013193 (1974)","journal-title":"Inf. Control"},{"key":"9071_CR8","unstructured":"Buhrman, H.: Resource bounded reductions. PhD thesis, University of Amsterdam (1993)"},{"key":"9071_CR9","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Fortnow, L., Pavan, A.: Some results on derandomization. In: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science. LNCS, vol.\u00a02607, pp. 212\u2013222 (2003)","DOI":"10.1007\/3-540-36494-3_20"},{"key":"9071_CR10","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.\u00a0643\u2013654 (1992)","DOI":"10.1145\/129712.129775"},{"issue":"1","key":"9071_CR11","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0890-5401(91)90022-T","volume":"92","author":"J. Geske","year":"1991","unstructured":"Geske, J., Huynh, D., Seiferas, J.: A note on almost-everywhere-complex sets and separating deterministic-time-complexity classes. Inf. Comput. 92(1), 97\u2013104 (1991)","journal-title":"Inf. Comput."},{"key":"9071_CR12","doi-asserted-by":"crossref","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. Inf. Process. Lett. 43, 169\u2013174 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9071_CR13","doi-asserted-by":"crossref","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. Comput. Complex. 12, 85\u2013130 (2003)","journal-title":"Comput. Complex."},{"key":"9071_CR14","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Gurevich, Y.: Average case completeness. J.\u00a0Comput. Syst. Sci. 42, 346\u2013398 (1991)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9071_CR15","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","volume":"65","author":"R. Impagliazzo","year":"2002","unstructured":"Impagliazzo, R., Kabanets, V., Wigderson, A.: In search of an easy witness: exponential time vs. probabilistic polynomial time. J.\u00a0Comput. Syst. Sci. 65, 672\u2013694 (2002)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9071_CR16","doi-asserted-by":"crossref","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 (1995)","DOI":"10.1109\/SCT.1995.514853"},{"key":"9071_CR17","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P\u2009=\u2009BPP if E requires exponential circuits: Derandomizing the XOR lemma. In: Proceedings of the 29th ACM Symposium on Theory of Computing, pp.\u00a0220\u2013229 (1997)","DOI":"10.1145\/258533.258590"},{"issue":"2","key":"9071_CR18","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2001.1763","volume":"63","author":"V. Kabanets","year":"2001","unstructured":"Kabanets, V.: Easiness assumptions and hardness tests: Trading time for zero error. J.\u00a0Comput. Syst. Sci. 63(2), 236\u2013252 (2001)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9071_CR19","doi-asserted-by":"crossref","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 J. Comput. 31, 1501\u20131526 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9071_CR20","doi-asserted-by":"crossref","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. Inf. Comput. 190(1), 1\u201317 (2004)","journal-title":"Inf. Comput."},{"key":"9071_CR21","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"Levin, L.: Average case complete problems. SIAM J. Comput. 15, 285\u2013286 (1986)","journal-title":"SIAM J. Comput."},{"key":"9071_CR22","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","first-page":"191","volume-title":"Distributed Computing and Cryptography","author":"R. Lipton","year":"1991","unstructured":"Lipton, R.: New directions in testing. In: Distributed Computing and Cryptography. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.\u00a02, pp.\u00a0191\u2013202. American Mathematics Society, Providence (1991)"},{"issue":"2","key":"9071_CR23","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.\u00a0Comput. Syst. Sci. 49(2), 149\u2013167 (1994)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9071_CR24","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"1","key":"9071_CR25","first-page":"146","volume":"25","author":"J. Seiferas","year":"1978","unstructured":"Seiferas, J., Fischer, M., Meyer, A.: Separating nondeterministic time complexity classes. J.\u00a0ACM 25(1), 146\u2013147 (1978)","journal-title":"J.\u00a0ACM"},{"key":"9071_CR26","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.\u00a0648\u2013657 (2001)","DOI":"10.1109\/SFCS.2001.959941"},{"key":"9071_CR27","doi-asserted-by":"crossref","unstructured":"Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. In: 20th IEEE Conference on Computational Complexity, pp.\u00a0212\u2013226 (2005)","DOI":"10.1109\/CCC.2005.26"},{"key":"9071_CR28","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.\u00a0458\u2013463 (1985)","DOI":"10.1145\/22145.22196"},{"key":"9071_CR29","doi-asserted-by":"crossref","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. Comput. Sci. 26, 327\u2013333 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"9071_CR30","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.\u00a0295\u2013328. Springer, Berlin (1997)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9071-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9071-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9071-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9071-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,13]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,5]]}},"alternative-id":["9071"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9071-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,13]]}}}