{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:28Z","timestamp":1742617228487,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540613329"},{"type":"electronic","value":"9783540684619"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61332-3_164","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:34:08Z","timestamp":1330292048000},"page":"300-309","source":"Crossref","is-referenced-by-count":1,"title":["Reductions and convergence rates of average time"],"prefix":"10.1007","author":[{"given":"Jay","family":"Belanger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"32_CR1","doi-asserted-by":"crossref","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. J. Comp. Sys. Sci., 44:193\u2013219, 1992. (First appeared in Proc. 21st STOC, ACM, pages 204\u2013216, 1989.)","journal-title":"J. Comp. Sys. Sci."},{"key":"32_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1137\/S0097539792232070","volume":"24","author":"A. Blass","year":"1995","unstructured":"A. Blass and Y. Gurevich. Matrix transformation is complete for the average case. SIAM J. Comput., 24:3\u201329, 1995.","journal-title":"SIAM J. Comput."},{"key":"32_CR3","unstructured":"J. Belanger and J. Wang. No NP problems averaging on ranking of distributions are harder. Submitted."},{"key":"32_CR4","doi-asserted-by":"crossref","unstructured":"J. Belanger and J. Wang. Rankable distributions do not provide harder instances than uniform distributions. Proc. 1st COCOON, vol 959 of Lect. Notes in Comp. Sci., pages 410\u2013419, 1995.","DOI":"10.1007\/BFb0030860"},{"key":"32_CR5","unstructured":"J.-Y. Cai and A. Selman. Average time complexity classes. Elect. Col. Comp. Complexity TR95-019, 1995."},{"key":"32_CR6","unstructured":"J.-Y. Cai and A. Selman. Personal communication."},{"key":"32_CR7","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(94)90048-5","volume":"49","author":"M. Goldmann","year":"1994","unstructured":"M. Goldmann, P. Grape, and J. H\u00e5stad. On average time hierarchies. Inf. Proc. Lett., 49:15\u201320, 1994.","journal-title":"Inf. Proc. Lett."},{"issue":"1","key":"32_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0890-5401(91)90022-T","volume":"92","author":"J. Geske","year":"1991","unstructured":"J. Geske, D. Huynh and J. Seiferas. A note on almost-everywhere complex sets with application to polynomial complexity degrees. Inf. and Comput., 92(1):97\u2013104, 1991.","journal-title":"Inf. and Comput."},{"issue":"3","key":"32_CR9","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Y. Gurevich and S. Shelah. Expected Computation Time for Hamiltonian Path Problem. SIAM J. on Computing, 16:3(1987), pp. 486\u2013502.","journal-title":"SIAM J. on Computing"},{"key":"32_CR10","unstructured":"Y. Gurevich. The challenger-solver game: variations on the theme of P =? NP. EATCS Bulletin, pages 112\u2013121, 1989."},{"key":"32_CR11","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevich","year":"1991","unstructured":"Y. Gurevich. Average case completeness. J. Comp. Sys. Sci., 42:346\u2013398, 1991.","journal-title":"J. Comp. Sys. Sci."},{"key":"32_CR12","first-page":"54","volume":"10","author":"G. Hardy","year":"1911","unstructured":"G. Hardy. Properties of logarithmico-exponential functions. Proc. London Math. Soc., 10:54\u201390, 1911.","journal-title":"Proc. London Math. Soc."},{"key":"32_CR13","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285\u2013306, 1965.","journal-title":"Trans. Amer. Math. Soc."},{"key":"32_CR14","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0196-6774(84)90032-4","volume":"5","author":"D. Johnson","year":"1984","unstructured":"D. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 5:284\u2013299, 1984.","journal-title":"Journal of Algorithms"},{"key":"32_CR15","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo. A personal view of average-case complexity. Proc. 10th Structures, IEEE, pages 134\u2013147, 1995.","DOI":"10.1109\/SCT.1995.514853"},{"key":"32_CR16","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 J. Comput., 15:285\u2013286, 1986. (First appeared in Proc. 16th STOC, ACM, page 465, 1984.)","journal-title":"SIAM J. Comput."},{"key":"32_CR17","unstructured":"R. Venkatesan. Average-Case Intractability. Ph.D. Thesis (Advisor: L. Levin), Boston University, 1991."},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"R. Venkatesan and L. Levin. Random instances of a graph coloring problem are hard. In Proc. 20th STOC, pages 217\u2013222, 1988.","DOI":"10.1145\/62212.62231"},{"key":"32_CR19","doi-asserted-by":"crossref","unstructured":"R. Venkatesan and S. Rajagopalan. Average case intractability of diophantine and matrix problems. In Proc. 24th STOC, pages 632\u2013642, 1992.","DOI":"10.1145\/129712.129774"},{"key":"32_CR20","unstructured":"J. Wang. Average-case computational complexity theory. Complexity Theory Retrospective II (A. Selman and L. Hemaspaandra eds), Springer-Verlag, to appear. (Also available by anonymous ftp at ftp.uncg.edu under the directory people\/wangjie with file name avg_comp.ps.gz.)"},{"key":"32_CR21","doi-asserted-by":"crossref","unstructured":"J. Wang. Average-case completeness of a word problem for groups. In Proc. 27th STOC, pages 325\u2013334, 1995.","DOI":"10.1145\/225058.225153"},{"key":"32_CR22","unstructured":"J. Wang and J. Belanger. On average-P vs. average-NP. In K. Ambos-Spies, S. Homer, and U. Sch\u00f6nings, editors, Complexity Theory\u2014Current Research, pages 47\u201367. Cambridge University Press, 1993."},{"key":"32_CR23","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1006\/jcss.1995.1014","volume":"50","author":"J. Wang","year":"1995","unstructured":"J. Wang and J. Belanger. On the NP-isomorphism problem with respect to random instances. J. Comp. Sys. Sci., 50(1995), pp. 151\u2013164.","journal-title":"J. Comp. Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61332-3_164.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:18:11Z","timestamp":1742599091000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61332-3_164"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540613329","9783540684619"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/3-540-61332-3_164","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}