{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:18:03Z","timestamp":1742617083753,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540562795"},{"type":"electronic","value":"9783540475019"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56279-6_79","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:57:53Z","timestamp":1330253873000},"page":"259-268","source":"Crossref","is-referenced-by-count":0,"title":["Honest iteration schemes of randomizing algorithms"],"prefix":"10.1007","author":[{"given":"Jie","family":"Wang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jay","family":"Belanger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"S. Ben-David, B. Chor, O. Goldreich, and M. Luby, On the theory of average case complexity, Proc. 21st Annual ACM Symposium on Theory of Computing, 1989, pp.204\u2013216.","DOI":"10.1145\/73007.73027"},{"key":"28_CR2","doi-asserted-by":"crossref","unstructured":"A. Blass and Y. Gurevich, Randomizing reductions of search problems, Proceedings of Foundations of Software Technology and Theoretical Computer Science (Invited Talk), New Delhi, India, 1991, pp. 10\u201324.","DOI":"10.1007\/3-540-54967-6_58"},{"key":"28_CR3","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. of Computer and System Sciences, 42(1991), pp. 346\u2013398.","journal-title":"J. of Computer and System Sciences"},{"key":"28_CR4","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo and L. Levin, No better ways to generate hard NP instances than picking uniformly at random, Proc. 31th IEEE Symposium on Foundations of Computer Science, 1990, pp. 812\u2013821.","DOI":"10.1109\/FSCS.1990.89604"},{"key":"28_CR5","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. on Computing, 15(1986), pp. 285\u2013286. Extended abstract appeared in Proc. 16th ACM Symposium on Theory of Computing, 1984, p. 465.","journal-title":"SIAM J. on Computing"},{"key":"28_CR6","doi-asserted-by":"crossref","unstructured":"R. Venkatesan and L. Levin, Random instances of a graph coloring problem are hard, Proc. 20th ACM Symposium on Theory of Computing, 1988, pp. 217\u2013222.","DOI":"10.1145\/62212.62231"},{"key":"28_CR7","unstructured":"R. Venkatesan, Average Case Intractability, Ph.D. thesis, Computer Science Department, Boston University, 1991."},{"key":"28_CR8","doi-asserted-by":"crossref","unstructured":"R. Venkatesan and S. Rajagopalan, Average case intractability of Diophantine and matrix problems, Proc. of 24th ACM Symposium of Theory of Computing, May 1992, pp. 632\u2013642.","DOI":"10.1145\/129712.129774"},{"key":"28_CR9","doi-asserted-by":"crossref","unstructured":"J. Wang and J. Belanger, On average P vs. average NP, Proc. of the 7th IEEE Conference on Structure in Complexity Theory, June 1992, pp. 318\u2013326.","DOI":"10.1109\/SCT.1992.215406"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56279-6_79.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:46:20Z","timestamp":1742593580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56279-6_79"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540562795","9783540475019"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-56279-6_79","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}