{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T14:13:14Z","timestamp":1778249594260,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602163","type":"print"},{"value":"9783540447337","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0030860","type":"book-chapter","created":{"date-parts":[[2005,12,1]],"date-time":"2005-12-01T03:51:40Z","timestamp":1133409100000},"page":"410-419","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Rankable distributions do not provide harder instances than uniform distributions"],"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,20]]},"reference":[{"key":"47_CR1","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. J. Comp. Sys. Sci., 44:193\u2013219, 1992.","journal-title":"J. Comp. Sys. Sci."},{"key":"47_CR2","unstructured":"A. Blass and Y. Gurevich. Randomizing reductions of decision problems (tentative title). Personal communication."},{"key":"47_CR3","doi-asserted-by":"publisher","first-page":"949","DOI":"10.1137\/0222059","volume":"22","author":"A. Blass","year":"1993","unstructured":"A. Blass and Y. Gurevich. Randomizing reductions of search problems. SIAM J. Comput., 22:949\u2013975, 1993.","journal-title":"SIAM J. Comput."},{"key":"47_CR4","doi-asserted-by":"crossref","unstructured":"A. Blass and Y. Gurevich. Matrix decomposition is complete for the average case. SIAM J. Comput., 1994. to appear.","DOI":"10.1137\/S0097539792232070"},{"key":"47_CR5","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM J. Comput., 6:305\u2013321, 1977.","journal-title":"SIAM J. Comput."},{"key":"47_CR6","unstructured":"B. Bollob\u00e1s. Random Graphs. Academic Press, 1985."},{"key":"47_CR7","unstructured":"J.-Y. Cai and A. Selman. Average time complexity classes. Manuscript."},{"key":"47_CR8","doi-asserted-by":"publisher","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. Hastad. On average time hierarchies. Inf. Proc. Lett., 49:15\u201320, 1994.","journal-title":"Inf. Proc. Lett."},{"key":"47_CR9","doi-asserted-by":"publisher","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. Comput., 16:486\u2013502, 1987.","journal-title":"SIAM J. Comput."},{"key":"47_CR10","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. J. Comp. Sys. Sci., 42:346\u2013398, 1991.","journal-title":"J. Comp. Sys. Sci."},{"key":"47_CR11","first-page":"54","volume":"10","author":"G. Hardy","year":"1911","unstructured":"G. Hardy. Properties of logarithmico-exponential functions. Proc. London Math. Soc., (2),10:54\u201390, 1911.","journal-title":"Proc. London Math. Soc., (2)"},{"key":"47_CR12","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. Sterns. On the computational complexity of algorithms. Trans. Amer. Math. Soc., 117:285\u2013306, 1965.","journal-title":"Trans. Amer. Math. Soc."},{"key":"47_CR13","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and L. Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proc. 31st FOCS, pages 812\u2013821, 1990.","DOI":"10.1109\/FSCS.1990.89604"},{"key":"47_CR14","unstructured":"R. Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991."},{"key":"47_CR15","unstructured":"N. Johnson and S. Kotz. Distributions in Statistics-Discrete Distributions. John Wiley & Sons, 1969."},{"key":"47_CR16","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":"47_CR17","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.","journal-title":"SIAM J. Comput."},{"key":"47_CR18","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. Vit\u00e1nyi. Average case complexity under the universal distribution equals worst-case complexity. Inf. Proc. Lett., 42:145\u2013149, 1992.","journal-title":"Inf. Proc. Lett."},{"key":"47_CR19","doi-asserted-by":"crossref","first-page":"650","DOI":"10.1007\/3-540-56503-5_64","volume":"665","author":"R. Reischuk","year":"1993","unstructured":"R. Reischuk and C. Schindelhauer. Precise average case complexity. STACS'93, vol 665 of Lect. Notes in Comp. Sci., pages 650\u2013661, 1993.","journal-title":"Lect. Notes in Comp. Sci."},{"key":"47_CR20","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/3-540-56287-7_100","volume":"652","author":"R. Schuler","year":"1992","unstructured":"R. Schuler and T. Yamakami. Structural average case complexity. FSTTCS'92, vol 652 of Lect. Notes in Comp. Sci., pages 128\u2013139, 1992.","journal-title":"Lect. Notes in Comp. Sci."},{"key":"47_CR21","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":"47_CR22","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":"47_CR23","doi-asserted-by":"crossref","unstructured":"J. Wang. Average-case completeness of a word problem for groups. In Proc. 27th STOC, 1995. To appear.","DOI":"10.1145\/225058.225153"},{"key":"47_CR24","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":"47_CR25","doi-asserted-by":"publisher","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:151\u2013164, 1995.","journal-title":"J. Comp. Sys. Sci."}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0030860","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T13:29:36Z","timestamp":1778246976000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/BFb0030860"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602163","9783540447337"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/bfb0030860","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"20 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}