{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T05:35:48Z","timestamp":1740461748838,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642153686"},{"type":"electronic","value":"9783642153693"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15369-3_54","type":"book-chapter","created":{"date-parts":[[2010,8,27]],"date-time":"2010-08-27T04:01:36Z","timestamp":1282881696000},"page":"724-737","source":"Crossref","is-referenced-by-count":1,"title":["Improved Rounding for Parallel Repeated Unique Games"],"prefix":"10.1007","author":[{"given":"David","family":"Steurer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"54_CR1","doi-asserted-by":"crossref","unstructured":"Austrin, P.: Towards sharp inapproximability for any 2-CSP. In: FOCS, pp. 307\u2013317 (2007)","DOI":"10.1109\/FOCS.2007.41"},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Barak, B., Hardt, M., Haviv, I., Rao, A., Regev, O., Steurer, D.: Rounding parallel repetitions of unique games. In: FOCS, pp. 374\u2013383 (2008)","DOI":"10.1109\/FOCS.2008.55"},{"key":"54_CR3","doi-asserted-by":"crossref","unstructured":"Charikar, M., Makarychev, K., Makarychev, Y.: Near-optimal algorithms for unique games. In: STOC, pp. 205\u2013214 (2006)","DOI":"10.1145\/1132516.1132547"},{"issue":"2","key":"54_CR4","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S. Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Computational Complexity\u00a015(2), 94\u2013114 (2006)","journal-title":"Computational Complexity"},{"key":"54_CR5","doi-asserted-by":"crossref","unstructured":"Feige, U., Kindler, G., O\u2019Donnell, R.: Understanding parallel repetition requires understanding foams. In: IEEE Conference on Computational Complexity, pp. 179\u2013192 (2007)","DOI":"10.1109\/CCC.2007.39"},{"key":"54_CR6","doi-asserted-by":"crossref","unstructured":"Feige, U., Lov\u00e1sz, L.: Two-prover one-round proof systems: Their power and their problems (extended abstract). In: STOC, pp. 733\u2013744 (1992)","DOI":"10.1145\/129712.129783"},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Guruswami, V., Manokaran, R., Raghavendra, P.: Beating the random ordering is hard: Inapproximability of maximum acyclic subgraph. In: FOCS, pp. 573\u2013582 (2008)","DOI":"10.1109\/FOCS.2008.51"},{"issue":"1","key":"54_CR8","doi-asserted-by":"publisher","first-page":"141","DOI":"10.4086\/toc.2009.v005a008","volume":"5","author":"T. Holenstein","year":"2009","unstructured":"Holenstein, T.: Parallel repetition: Simplification and the no-signaling case. Theory of Computing\u00a05(1), 141\u2013172 (2009)","journal-title":"Theory of Computing"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: STOC, pp. 767\u2013775 (2002)","DOI":"10.1145\/510014.510017"},{"issue":"1","key":"54_CR10","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1137\/S0097539705447372","volume":"37","author":"S. Khot","year":"2007","unstructured":"Khot, S., Kindler, G., Mossel, E., O\u2019Donnell, R.: Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput.\u00a037(1), 319\u2013357 (2007)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"54_CR11","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.jcss.2007.06.019","volume":"74","author":"S. Khot","year":"2008","unstructured":"Khot, S., Regev, O.: Vertex cover might be hard to approximate to within 2\u2009\u2212\u2009\u03b5. J. Comput. Syst. Sci.\u00a074(3), 335\u2013349 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.K.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into \u21131. In: FOCS, pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"Manokaran, R., Naor, J., Raghavendra, P., Schwartz, R.: SDP gaps and UGC-hardness for multiway cut, 0-extension, and metric labeling. In: STOC, pp. 11\u201320 (2008)","DOI":"10.1145\/1374376.1374379"},{"key":"54_CR14","doi-asserted-by":"crossref","unstructured":"Mossel, E., O\u2019Donnell, R., Oleszkiewicz, K.: Noise stability of functions with low influences invariance and optimality. In: FOCS, pp. 21\u201330 (2005)","DOI":"10.1109\/SFCS.2005.53"},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: STOC, pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"key":"54_CR16","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph Expansion and the Unique Games Conjecture. In: STOC (to appear, 2010)","DOI":"10.1145\/1806689.1806792"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Rao, A.: Parallel repetition in projection games and a concentration bound. In: STOC, pp. 1\u201310 (2008)","DOI":"10.1145\/1374376.1374378"},{"issue":"3","key":"54_CR18","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(3), 763\u2013803 (1998)","journal-title":"SIAM J. Comput."},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Raz, R.: A counterexample to strong parallel repetition. In: FOCS, pp. 369\u2013373 (2008)","DOI":"10.1109\/FOCS.2008.49"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15369-3_54.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,25]],"date-time":"2025-02-25T03:48:03Z","timestamp":1740455283000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15369-3_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642153686","9783642153693"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15369-3_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}