{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T16:59:34Z","timestamp":1725728374183},"publisher-location":"Berlin, Heidelberg","reference-count":7,"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_18","type":"book-chapter","created":{"date-parts":[[2013,6,2]],"date-time":"2013-06-02T21:03:04Z","timestamp":1370206984000},"page":"203-211","source":"Crossref","is-referenced-by-count":1,"title":["Improving on Gutfreund, Shaltiel,and Ta-Shma\u2019s Paper \u201cIf NP Languages Are Hard on the Worst-Case, Then It Is Easy to Find Their Hard Instances\u201d"],"prefix":"10.1007","author":[{"given":"Nikolay","family":"Vereshchagin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"18_CR1","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"},{"issue":"1","key":"18_CR2","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"A. Leonid","year":"1986","unstructured":"Leonid, A.: Levin, Average Case Complete Problems. SIAM J. Comput.\u00a015(1), 285\u2013286 (1986)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Ben-David, S., Chor, B., Luby, O.G.M.: On the Theory of Average Case Complexity. In: STOC, pp. 204\u2013216 (1989)","key":"18_CR3","DOI":"10.1145\/73007.73027"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1007\/11830924_36","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"D. Gutfreund","year":"2006","unstructured":"Gutfreund, D.: Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy. In: D\u00edaz, J., Jansen, K., Rolim, J.D.P., Zwick, U. (eds.) APPROX 2006 and RANDOM 2006. LNCS, vol.\u00a04110, pp. 386\u2013397. Springer, Heidelberg (2006)"},{"unstructured":"Bogdanov, A., Talwar, K., Wan, A.: Hard instances for satisfiability and quasi-one-way functions. In: Proceedings of Innovations in Computer Science (ICS 2009), pp. 290\u2013300. Tsinghua University Press (2009)","key":"18_CR5"},{"issue":"4","key":"18_CR6","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/s00037-007-0235-8","volume":"16","author":"D. Gutfreund","year":"2007","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. Computational Complexity (CC)\u00a016(4), 412\u2013441 (2007)","journal-title":"Computational Complexity (CC)"},{"doi-asserted-by":"crossref","unstructured":"Adleman, L.M.: Two Theorems on Random Polynomial Time. In: FOCS 1978, pp. 75\u201383 (1978)","key":"18_CR7","DOI":"10.1109\/SFCS.1978.37"}],"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_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T07:42:54Z","timestamp":1563090174000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38536-0_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385353","9783642385360"],"references-count":7,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38536-0_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}