{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T05:29:32Z","timestamp":1736573372985,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540648277"},{"type":"electronic","value":"9783540685326"}],"license":[{"start":{"date-parts":[[1998,1,1]],"date-time":"1998-01-01T00:00:00Z","timestamp":883612800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0055766","type":"book-chapter","created":{"date-parts":[[2006,8,17]],"date-time":"2006-08-17T17:36:31Z","timestamp":1155836191000},"page":"176-184","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Minimum propositional proof length is NP-hard to linearly approximate"],"prefix":"10.1007","author":[{"given":"Michael","family":"Alekhnovich","sequence":"first","affiliation":[]},{"given":"Sam","family":"Buss","sequence":"additional","affiliation":[]},{"given":"Shlomo","family":"Moran","sequence":"additional","affiliation":[]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,5,28]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1006\/jcss.1997.1472","volume":"54","author":"S. Arora","year":"1997","unstructured":"S. Arora, L. Babai, J. Stern, and Z. Sweedyk, The hardness of approximate optima in lattices, codes, and systems of linear equations, Journal of Computer and System Sciences, 54 (1997), pp. 317\u2013331. Earlier version in Proc. 34th Symp. Found. of Comp. Sci., 1993, pp.724\u2013733.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR2","volume-title":"Approximation Algorithms for NP-hard Problems","author":"S. Arora","year":"1996","unstructured":"S. Arora and C. Lund, Hardness of approximations, in Approximation Algorithms for NP-hard Problems, D. S. Hochbaum, ed., PWS Publishing Co., Boston, 1996, p. ???"},{"key":"13_CR3","first-page":"274","volume-title":"Simplified and improved resolution lower bounds","author":"P. Beame","year":"1996","unstructured":"P. Beame and T. Pitassi, Simplified and improved resolution lower bounds, in Proceedings, 37th Annual Symposium on Foundations of Computer Science, Los Alamitos, California, 1996, IEEE Computer Society, pp. 274\u2013282."},{"key":"13_CR4","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/230514.571641","volume":"27","author":"M. Bellare","year":"1996","unstructured":"M. Bellare, Proof checking and approximation: Towards tight results, SIGACT News, 27 (1996), pp. 2\u201313. Revised version at http:\/\/www-cse.ucsd.edu\/users\/mihir.","journal-title":"SIGACT News"},{"doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell, Efficient probabalistically checkable proofs and applications to approximation, in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1993, pp. 294\u2013304.","key":"13_CR5","DOI":"10.1145\/195058.195467"},{"key":"13_CR6","first-page":"264","volume-title":"No feasible interpolation for TC0-Frege proofs","author":"M. L. Bonet","year":"1997","unstructured":"M. L. Bonet, T. Pitassi, and R. Raz, No feasible interpolation for TC0-Frege proofs, in Proceedings of the 38th Annual Symposium on Foundations of Computer Science, Piscataway, New Jersey, 1997, IEEE Computer Society, pp. 264\u2013263."},{"key":"13_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-1-4612-2566-9_4","volume-title":"Feasible Mathematics II","author":"S. R. Buss","year":"1995","unstructured":"S. R. Buss, On G\u00f6del's theorems on lengths of proofs II: Lower bounds for recognizing k symbol provability, in Feasible Mathematics II, P. Clote and J. Remmel, eds., Birkh\u00e4auser-Boston, 1995, pp. 57\u201390."},{"doi-asserted-by":"crossref","unstructured":"M. Clegg, J. Edmonds, and R. Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, in Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, Association for Computing Machinery, 1996, pp. 174\u2013183.","key":"13_CR8","DOI":"10.1145\/237814.237860"},{"doi-asserted-by":"crossref","unstructured":"U. Feige, A threshold of ln n for approximating set cover, in Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1996, pp. 314\u2013318.","key":"13_CR9","DOI":"10.1145\/237814.237977"},{"doi-asserted-by":"crossref","unstructured":"K. Iwama, Complexity of finding short resolution proofs, in Mathematical Foundations of Computer Science 1997, I. Pr\u00edvara and P. Ruzicka, eds., Lecture Notes in Computer Science #1295, Springer-Verlag, 1997, pp. 309\u2013318.","key":"13_CR10","DOI":"10.1007\/BFb0029974"},{"key":"13_CR11","first-page":"29","volume-title":"Intractibility of read-once resolution","author":"K. Iwama","year":"1995","unstructured":"K. Iwama and E. Miyano, Intractibility of read-once resolution, in Proceedings of the Tenth Annual Conference on Structure in Complexity Theory, Los Alamitos, California, 1995, IEEE Computer Society, pp. 29\u201336."},{"doi-asserted-by":"crossref","unstructured":"S. Khanna, M. Sudan, and L. Trevisan, Constraint satisfaction: The approximability of minimization problems, in Twelfth Annual Conference on Computational Complexity, IEEE Computer Society, 1997, pp. 282\u2013296.","key":"13_CR12","DOI":"10.1109\/CCC.1997.612323"},{"key":"13_CR13","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1007\/3-540-60178-3_86","volume-title":"Logic and Computational Complexity","author":"J. Kraj\u00ed\u010dek","year":"1995","unstructured":"J. Kraj\u00ed\u010dek and P. Pudl\u00e1k, Some consequences of cryptographic conjectures for S 2 1 and EF, in Logic and Computational Complexity, D. Leivant, ed., Berlin, 1995, Springer-Verlag, pp. 210\u2013220."},{"key":"13_CR14","doi-asserted-by":"crossref","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis, On the hardness of approximating minimization problems, Journal of the Association for Computing Machinery, 41 (1994), pp. 960\u2013981.","journal-title":"Journal of the Association for Computing Machinery"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1998"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0055766","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T13:52:06Z","timestamp":1736517126000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0055766"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540648277","9783540685326"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/bfb0055766","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]},"assertion":[{"value":"28 May 2006","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}