{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:35:02Z","timestamp":1725744902197},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642404498"},{"type":"electronic","value":"9783642404504"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40450-4_58","type":"book-chapter","created":{"date-parts":[[2013,8,16]],"date-time":"2013-08-16T03:22:47Z","timestamp":1376623367000},"page":"683-694","source":"Crossref","is-referenced-by-count":0,"title":["Improved Approximation Algorithms for Projection Games"],"prefix":"10.1007","author":[{"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","reference":[{"key":"58_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: Proc. 51st IEEE Symp. on Foundations of Computer Science (2010)","DOI":"10.1109\/FOCS.2010.59"},{"issue":"3","key":"58_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. Journal of the ACM\u00a045(3), 501\u2013555 (1998)","journal-title":"Journal of the ACM"},{"issue":"1","key":"58_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. Journal of the ACM\u00a045(1), 70\u2013122 (1998)","journal-title":"Journal of the ACM"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proc. 23rd ACM Symp. on Theory of Computing, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"58_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.: Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity\u00a01, 3\u201340 (1991)","journal-title":"Computational Complexity"},{"issue":"3","key":"58_CR6","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.\u00a027(3), 804\u2013915 (1998)","journal-title":"SIAM J. Comput."},{"key":"58_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-642-04128-0_3","volume-title":"Algorithms - ESA 2009","author":"M. Charikar","year":"2009","unstructured":"Charikar, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for label cover problems. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol.\u00a05757, pp. 23\u201334. Springer, Heidelberg (2009)"},{"key":"58_CR8","doi-asserted-by":"crossref","unstructured":"Dinur, I., Steurer, D.: Analytical approach to parallel repetition. Tech. Rep. 1305.1979, arXiv (2013)","DOI":"10.1145\/2591796.2591884"},{"issue":"4","key":"58_CR9","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. Journal of the ACM\u00a045(4), 634\u2013652 (1998)","journal-title":"Journal of the ACM"},{"key":"58_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/800119.803884","volume-title":"Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974","author":"M.R. Garey","year":"1974","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified np-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 47\u201363. ACM, New York (1974)"},{"issue":"4","key":"58_CR11","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J. H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. Journal of the ACM\u00a048(4), 798\u2013859 (2001)","journal-title":"Journal of the ACM"},{"key":"58_CR12","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1145\/1007352.1007362","volume-title":"Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2004","author":"J. Holmerin","year":"2004","unstructured":"Holmerin, J., Khot, S.: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2004, pp. 11\u201320. ACM, New York (2004)"},{"key":"58_CR13","unstructured":"Khot, S.: Hardness results for coloring 3-colorable 3-uniform hypergraphs. In: Proc. 43rd IEEE Symp. on Foundations of Computer Science, pp. 23\u201332 (2002)"},{"key":"58_CR14","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proc. 34th ACM Symp. on Theory of Computing, pp. 767\u2013775 (2002)","DOI":"10.1145\/509907.510017"},{"key":"58_CR15","unstructured":"Klein, P.N.: A linear-time approximation scheme for TSP for planar weighted graphs. In: Proceedings of the 46th IEEE Symposium on Foundations of Computer Science, pp. 146\u2013155 (2005)"},{"key":"58_CR16","doi-asserted-by":"crossref","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.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 276\u2013287. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-32512-0_24"},{"key":"58_CR17","doi-asserted-by":"crossref","unstructured":"Moshkovitz, D., Raz, R.: Two query PCP with sub-constant error. Journal of the ACM\u00a057(5) (2010)","DOI":"10.1145\/1754399.1754402"},{"issue":"1","key":"58_CR18","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. of Discrete Algorithms\u00a05(1), 55\u201364 (2007)","journal-title":"J. of Discrete Algorithms"},{"key":"58_CR19","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.\u00a027, 763\u2013803 (1998)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2013"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40450-4_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,3]],"date-time":"2022-03-03T21:19:11Z","timestamp":1646342351000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40450-4_58"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642404498","9783642404504"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40450-4_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}