{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T04:30:42Z","timestamp":1764131442266,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,11,4]],"date-time":"2015-11-04T00:00:00Z","timestamp":1446595200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2015,11,4]],"date-time":"2015-11-04T00:00:00Z","timestamp":1446595200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1218547"],"award-info":[{"award-number":["1218547"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00453-015-0088-5","type":"journal-article","created":{"date-parts":[[2015,11,4]],"date-time":"2015-11-04T21:04:05Z","timestamp":1446671045000},"page":"555-594","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Improved Approximation Algorithms for Projection Games"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1052-2801","authenticated-orcid":false,"given":"Pasin","family":"Manurangsi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Moshkovitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,4]]},"reference":[{"key":"88_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: Proceedings of the 51st IEEE Symposium on Foundations of Computer Science, FOCS \u201910, pp.\u00a0563\u2013572. IEEE Computer Society, Washington, DC, USA (2010)","DOI":"10.1109\/FOCS.2010.59"},{"issue":"3","key":"88_CR2","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"88_CR3","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"88_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd ACM Symposium on Theory of Computing, STOC \u201991, pp.\u00a021\u201332. ACM, New York, NY, USA (1991)","DOI":"10.1145\/103418.103428"},{"issue":"1","key":"88_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1(1), 3\u201340 (1991)","journal-title":"Comput. Complex."},{"issue":"1","key":"88_CR6","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"3","key":"88_CR7","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1137\/S0097539796302531","volume":"27","author":"M Bellare","year":"1998","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, pcps, and nonapproximability-towards tight results. SIAM J. Comput. 27(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"88_CR8","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s00453-010-9464-3","volume":"61","author":"M Charikar","year":"2011","unstructured":"Charikar, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for label cover problems. Algorithmica 61(1), 190\u2013206 (2011)","journal-title":"Algorithmica"},{"key":"88_CR9","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. In: Proceedings of the 46th ACM Symposium on Theory of Computing, STOC \u201914, pp. 624\u2013633. ACM, New York, NY, USA (2014)","DOI":"10.1145\/2591796.2591884"},{"issue":"3","key":"88_CR10","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica 27(3), 275\u2013291 (2000)","journal-title":"Algorithmica"},{"issue":"4","key":"88_CR11","doi-asserted-by":"publisher","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of $$\\ln n$$ for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"issue":"3","key":"88_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"88_CR13","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48(4), 798\u2013859 (2001)","journal-title":"J. ACM"},{"key":"88_CR14","doi-asserted-by":"crossref","unstructured":"Holmerin, J., Khot, S.: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. In: Proceedings of the 36th ACM Symposium on Theory of Computing, STOC \u201904, pp.\u00a011\u201320. ACM, New York, NY, USA (2004)","DOI":"10.1145\/1007352.1007362"},{"key":"88_CR15","unstructured":"Khot, S.: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, FOCS \u201902, pp.\u00a023\u201332. IEEE Computer Society, Washington, DC, USA (2002)"},{"key":"88_CR16","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 34th ACM Symposium on Theory of Computing, STOC \u201902, pp.\u00a0767\u2013775. ACM, New York, NY, USA (2002)","DOI":"10.1145\/509907.510017"},{"key":"88_CR17","doi-asserted-by":"crossref","unstructured":"Marx, D.: On the optimality of planar and geometric approximation schemes. In: Proceedings of the 48th IEEE Symposium on Foundations of Computer Science, FOCS \u201907, pp.\u00a0338\u2013348. IEEE Computer Society, Washington, DC, USA (2007)","DOI":"10.1109\/FOCS.2007.26"},{"key":"88_CR18","doi-asserted-by":"publisher","first-page":"276","DOI":"10.1007\/978-3-642-32512-0_24","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques vol.\u00a07408 of Lecture Notes in Computer Science","author":"D Moshkovitz","year":"2012","unstructured":"Moshkovitz, D.: The projection games conjecture and the NP-hardness of $$\\ln n$$-approximating set-cover. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques vol.\u00a07408 of Lecture Notes in Computer Science, pp. 276\u2013287. Springer, Berlin (2012)"},{"issue":"5","key":"88_CR19","first-page":"29:1","volume":"57","author":"D Moshkovitz","year":"2008","unstructured":"Moshkovitz, D., Raz, R.: Two-query PCP with subconstant error. J. ACM 57(5), 29:1\u201329:29 (2008)","journal-title":"J. ACM"},{"issue":"1","key":"88_CR20","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.jda.2006.03.008","volume":"5","author":"D Peleg","year":"2007","unstructured":"Peleg, D.: Approximation algorithms for the label-cover max and red-blue set cover problems. J. Discret. Algorithms 5(1), 55\u201364 (2007)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"88_CR21","doi-asserted-by":"publisher","first-page":"763","DOI":"10.1137\/S0097539795280895","volume":"27","author":"R Raz","year":"1998","unstructured":"Raz, R.: A parallel repetition theorem. SIAM J. Comput. 27(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0088-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0088-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0088-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0088-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:32:15Z","timestamp":1589697135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0088-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,4]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["88"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0088-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2015,11,4]]},"assertion":[{"value":"22 August 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2015","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 November 2015","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}