{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:40:35Z","timestamp":1736408435632,"version":"3.32.0"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540646822"},{"type":"electronic","value":"9783540691068"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/bfb0054368","type":"book-chapter","created":{"date-parts":[[2006,6,7]],"date-time":"2006-06-07T07:43:28Z","timestamp":1149666208000},"page":"205-209","source":"Crossref","is-referenced-by-count":1,"title":["Some recent strong inapproximability results"],"prefix":"10.1007","author":[{"given":"Johan","family":"H\u00e5stad","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2006,5,26]]},"reference":[{"key":"19_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan and M. Szegedy. Proof verification and intractability of approximation problems. Proceedings of 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 1992, pp 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"19_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. Proceedings of 33rd Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, 1992, 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"19_CR3","doi-asserted-by":"crossref","unstructured":"M. Bellare, O. Goldreich and M. Sudan. Free Bits, PCPs and Non-Approximability\u2014Towards tight Results. Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, Milwaukee, pp 422\u2013431. See also a more complete version available from ECCC, Electronic Colloquium on Computational Complexity (http:\/\/www.eccc.uni-trier.de\/eccc).","DOI":"10.1109\/SFCS.1995.492573"},{"key":"19_CR4","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund and A. Russell. Efficient probabilistically checkable proofs and applications to approximation. Proceedings of the 25th Annual ACM Symposium on Theory of Computation, San Diego, 1993, pp 294\u2013304. (See also Errata sheet in Proceedings of the 26th Annual ACM Symposium on Theory of Computation, Montreal, 1994, pp 820).","DOI":"10.1145\/167088.167174"},{"key":"19_CR5","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan. Improved non-approximability results. Proceedings of 26th Annual ACM Symposium on Theory of Computation, Montreal, 1994, pp 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"19_CR6","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multiprover interactive proofs. How to remove intractability. Proceedings of the 20th Annual ACM Symposium on Theory of Computation, Chicago, 1988, pp 113\u2013131.","DOI":"10.1145\/62212.62223"},{"issue":"2","key":"19_CR7","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U. Feige","year":"1996","unstructured":"U. Feige, S. Goldwasser, L. Lov\u00e1sz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 1996, Vol 43:2, pp 268\u2013292.","journal-title":"Journal of the ACM"},{"key":"19_CR8","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel, and M. Sipser. On the power of Multi-Prover Interactive Protocols. Proceedings 3rd IEEE Symposium on Structure in Complexity Theory, pp 156\u2013161, 1988.","DOI":"10.1109\/SCT.1988.5275"},{"key":"19_CR9","unstructured":"M.R. Garey and D.S. Johnsson. Computers and Intractability. W.H. Freeman and Company, 1979."},{"key":"19_CR10","unstructured":"J. H\u00e5stad. Some optimal inapproximability results. Proceedings of 29th Annual ACM Symposium on Theory of Computation, El Paso, 1997, pp 1\u201310. See also a more complete version available from ECCC, Electronic Colloquium on Computational Complexity (http:\/\/www.eccc.uni-trier.de\/eccc)."},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"D.S. Johnsson","year":"1974","unstructured":"D.S. Johnsson. Approximation algorithms for combinatorial problems. J. Computer and System Sciences, 1974, Vol 9, pp 256\u2013278.","journal-title":"J. Computer and System Sciences"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, Vol 43, 1991, pp 425\u2013440.","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"R. Raz. A parallel repetition theorem. Proceedings of 27th Annual ACM Symposium on Theory of Computation, Las Vegas, 1995, pp 447\u2013456.","DOI":"10.1145\/225058.225181"},{"key":"19_CR14","doi-asserted-by":"crossref","unstructured":"L. Trevisan, G. Sorkin, M. Sudan, and D. Williamson. Gadgets, approximation and linear programming. Proceedings of 37th Annual IEEE Symposium on Foundations of Computer Science, Burlington, 1996, pp 617\u2013626.","DOI":"10.1109\/SFCS.1996.548521"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'98"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0054368","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:20:15Z","timestamp":1736407215000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0054368"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540646822","9783540691068"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/bfb0054368","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1998]]}}}