{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:24Z","timestamp":1725728364107},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385353"},{"type":"electronic","value":"9783642385360"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38536-0_17","type":"book-chapter","created":{"date-parts":[[2013,6,2]],"date-time":"2013-06-02T21:03:04Z","timestamp":1370206984000},"page":"195-202","source":"Crossref","is-referenced-by-count":0,"title":["On the Encoding Invariance of Polynomial Time Computable Distribution Ensembles"],"prefix":"10.1007","author":[{"given":"Anton","family":"Makhlin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"17_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":"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"},{"issue":"2","key":"17_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/0400000004","volume":"1","author":"A. Bogdanov","year":"2006","unstructured":"Bogdanov, A., Trevisan, L.: Average-Case Complexity. Foundations and Trends in Theoretical Computer Science\u00a01(2), 1\u2013106 (2006)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Gurevich, Y.: Complete and Incomplete Randomized NP Problems. In: Proceedings of 28th Annual Symposium on Foundations of Computer Science, pp. 111\u2013117 (1987)","DOI":"10.1109\/SFCS.1987.14"},{"issue":"3","key":"17_CR4","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(3), 346\u2013398 (1991)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"17_CR5","doi-asserted-by":"publisher","first-page":"486","DOI":"10.1137\/0216034","volume":"16","author":"Y. Gurevich","year":"1987","unstructured":"Gurevich, Y., Shelah, S.: Expected computation time for Hamiltonian path problem. SIAM Journal on Computing\u00a016(3), 486\u2013502 (1987)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Levin, L.A.: No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. In: Proceedings of 31st Annual Symposium on Foundations of Computer Science, pp. 812\u2013821 (1990)","DOI":"10.1109\/FSCS.1990.89604"},{"issue":"1","key":"17_CR7","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L.A. Levin","year":"1986","unstructured":"Levin, L.A.: Average Case Complete Problems. SIAM Journal on Computing\u00a015(1), 285\u2013286 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Venkatesan, R., Levin, L.: Random instances of a graph coloring problem are hard. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 217\u2013222 (1988)","DOI":"10.1145\/62212.62231"},{"key":"17_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-642-13182-0_37","volume-title":"Computer Science \u2013 Theory and Applications","author":"N. Vereshchagin","year":"2010","unstructured":"Vereshchagin, N.: An Encoding Invariant Version of Polynomial Time Computable Distributions. In: Ablayev, F., Mayr, E.W. (eds.) CSR 2010. LNCS, vol.\u00a06072, pp. 371\u2013383. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38536-0_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T12:34:30Z","timestamp":1557750870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}