{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774375},"publisher-location":"Berlin, Heidelberg","reference-count":7,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540544876"},{"type":"electronic","value":"9783540384014"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1991]]},"DOI":"10.1007\/3-540-54487-9_50","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T22:54:10Z","timestamp":1330210450000},"page":"17-30","source":"Crossref","is-referenced-by-count":8,"title":["On the reduction theory for average case complexity"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Blass","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuri","family":"Gurevich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","unstructured":"Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, \u201cOn the Theory of Average Case Complexity\u201d, Symposium on Theory of Computing, ACM, 1989, 204\u2013216.","DOI":"10.1145\/73007.73027"},{"key":"2_CR2","unstructured":"Yuri Gurevich, \u201cAverage Case Complexity\u201d, J. Computer and System Sciences (a special issue on FOCS'87) to appear."},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Yuri Gurevich, \u201cMatrix Decomposition Problem is Complete for the Average Case\u201d, Symposium on Foundations of Computer Science, IEEE Computer Society Press, 1990, 802\u2013811.","DOI":"10.1109\/FSCS.1990.89603"},{"key":"2_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"[GJ]Michael R. Garey and David S. Johnson, \u201cComputers and Intractability: A Guide to the Theory of NP-Completeness\u201d, Freeman, New York, 1979."},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Russel Impagliazzo and Leonid A. Levin, \u201cNo Better Ways to Generate Hard NP Instances than Picking Uniformly at Random\u201d, Symposium on Foundations of Computers Science, IEEE Computer Soviety Press, 1990, 812\u2013821.","DOI":"10.1109\/FSCS.1990.89604"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Leonid A. Levin, \u201cAverage Case Complete Problems\u201d, SIAM Journal of Computing, 1986.","DOI":"10.1137\/0215020"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Ramarathnam Venkatesan and Leonid Levin, \u201cRandom Instances of a Graph Coloring Problem are Hard\u201d, Symposium on Theory of Computing, ACM, 1988, 217\u2013222.","DOI":"10.1145\/62212.62231"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-54487-9_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:55:02Z","timestamp":1605646502000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-54487-9_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991]]},"ISBN":["9783540544876","9783540384014"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/3-540-54487-9_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1991]]}}}