{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:56:15Z","timestamp":1780073775977,"version":"3.54.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Sloan Foundation Fellowship"},{"name":"NSF","award":["CCF-0832797, 0830673, and 0528414"],"award-info":[{"award-number":["CCF-0832797, 0830673, and 0528414"]}]},{"name":"Packard Fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"\n Subexponential time approximation algorithms are presented for the U\n nique<\/jats:sc>\n G\n ames<\/jats:sc>\n and S\n mall<\/jats:sc>\n -S\n et<\/jats:sc>\n E\n xpansion<\/jats:sc>\n problems. Specifically, for some absolute constant\n c<\/jats:italic>\n , the following two algorithms are presented.\n <\/jats:p>\n \n (1) An exp(\n kn<\/jats:italic>\n \u03f5<\/jats:sup>\n )-time algorithm that, given as input a\n k<\/jats:italic>\n -alphabet unique game on\n n<\/jats:italic>\n variables that has an assignment satisfying 1-\u03f5\n c<\/jats:sup>\n fraction of its constraints, outputs an assignment satisfying 1-\u03f5 fraction of the constraints.\n <\/jats:p>\n \n (2) An exp(\n n<\/jats:italic>\n \u03f5<\/jats:sup>\n \/\u03b4)-time algorithm that, given as input an\n n<\/jats:italic>\n -vertex regular graph that has a set\n S<\/jats:italic>\n of \u03b4\n n<\/jats:italic>\n vertices with edge expansion at most\n \n \u03f5\n c<\/jats:sup>\n <\/jats:italic>\n , outputs a set\n S'<\/jats:italic>\n of at most \u03b4\n n<\/jats:italic>\n vertices with edge expansion at most \u03f5.\n <\/jats:p>\n \n subexponential algorithm is also presented with improved approximation to M\n ax<\/jats:sc>\n C\n ut<\/jats:sc>\n , S\n parsest<\/jats:sc>\n C\n ut<\/jats:sc>\n , and V\n ertex<\/jats:sc>\n C\n over<\/jats:sc>\n on some interesting subclasses of instances. These instances are graphs with low\n threshold rank<\/jats:italic>\n , an interesting new graph parameter highlighted by this work.\n <\/jats:p>\n \n Khot's Unique Games Conjecture (UGC) states that it is\n NP<\/jats:bold>\n -hard to achieve approximation guarantees such as ours for U\n nique<\/jats:sc>\n G\n ames<\/jats:sc>\n . While the results here stop short of refuting the UGC, they do suggest that U\n nique<\/jats:sc>\n G\n ames<\/jats:sc>\n are significantly easier than\n NP<\/jats:bold>\n -hard problems such as M\n ax<\/jats:sc>\n 3-S\n at<\/jats:sc>\n , M\n ax<\/jats:sc>\n 3-\n Lin<\/jats:sc>\n , L\n abel<\/jats:sc>\n C\n over<\/jats:sc>\n , and more, which are believed not to have a subexponential algorithm achieving a nontrivial approximation ratio.\n <\/jats:p>\n \n Of special interest in these algorithms is a new notion of graph decomposition that may have other applications. Namely, it is shown for every \u03f5 >0 and every regular\n n<\/jats:italic>\n -vertex graph\n G<\/jats:italic>\n , by changing at most \u03b4 fraction of\n G<\/jats:italic>\n 's edges, one can break\n G<\/jats:italic>\n into disjoint parts so that the stochastic adjacency matrix of the induced graph on each part has at most\n n<\/jats:italic>\n \u03f5<\/jats:sup>\n eigenvalues larger than 1-\u03b7, where \u03b7 depends polynomially on \u03f5. The subexponential algorithm combines this decomposition with previous algorithms for U\n nique<\/jats:sc>\n G\n ames<\/jats:sc>\n on graphs with few large eigenvalues [Kolla and Tulsiani 2007; Kolla 2010].\n <\/jats:p>","DOI":"10.1145\/2775105","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Subexponential Algorithms for Unique Games and Related Problems"],"prefix":"10.1145","volume":"62","author":[{"given":"Sanjeev","family":"Arora","sequence":"first","affiliation":[{"name":"Princeton University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boaz","family":"Barak","sequence":"additional","affiliation":[{"name":"Microsoft Research New England"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Steurer","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579166"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793525309000096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90092-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334204"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.83"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133077"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132547"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.9"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.36"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.07.018"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 9th SODA. 510--520","author":"Dimitriou Ted","year":"1998","unstructured":"Ted Dimitriou and Russell Impagliazzo . 1998 . Go with the winners for graph bisection . In Proceedings of the 9th SODA. 510--520 . Ted Dimitriou and Russell Impagliazzo. 1998. Go with the winners for graph bisection. In Proceedings of the 9th SODA. 510--520."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of RANDOM-APPROX. 117--127","author":"Feige U.","unstructured":"U. Feige and D. Reichman . 2004. On systems of linear equations with two variables per equation . In Proceedings of RANDOM-APPROX. 117--127 . U. Feige and D. Reichman. 2004. On systems of linear equations with two variables per equation. In Proceedings of RANDOM-APPROX. 117--127."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00111-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/EJP.v11-300"},{"key":"e_1_2_1_21_1","volume-title":"Lee","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta , Robert Krauthgamer , and James R . Lee . 2003 . Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the FOCS. 534--543. Anupam Gupta, Robert Krauthgamer, and James R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the FOCS. 534--543."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109569"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.51"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780628"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.37"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.74"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.20"},{"key":"e_1_2_1_34_1","unstructured":"Alexandra Kolla and Madhur Tulsiani. 2007. Playing random and expanding unique games. Unpublished manuscript available from the authors' webpages. Subsumed by {Arora et al. 2008}. Alexandra Kolla and Madhur Tulsiani. 2007. Playing random and expanding unique games. Unpublished manuscript available from the authors' webpages. Subsumed by {Arora et al. 2008}."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536512"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2665063"},{"key":"e_1_2_1_37_1","volume-title":"Lenstra","author":"Lenstra A. K.","year":"1993","unstructured":"A. K. Lenstra and H. W. Jr . Lenstra . 1993 . The Development of the Number Field Sieve. Springer-Verlag , Berlin. A. K. Lenstra and H. W. Jr. Lenstra. 1993. The Development of the Number Field Sieve. Springer-Verlag, Berlin."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214079"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90009-5"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374379"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.60"},{"key":"e_1_2_1_43_1","unstructured":"E. Mossel R. O'Donnell and K. Oleszkiewicz. 2008. Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 101 (2008). E. Mossel R. O'Donnell and K. Oleszkiewicz. 2008. Noise stability of functions with low influences: Invariance and optimality. Ann. Math. 101 (2008)."},{"key":"e_1_2_1_44_1","unstructured":"Assaf Naor. 2004. On the Banach space valued Azuma inequality and small set isoperimetry in Alon-Roichman graphs. Available as eprint http:\/\/arxiv.org\/abs\/1009.5695v1arXiv:1009.5695v1. Assaf Naor. 2004. On the Banach space valued Azuma inequality and small set isoperimetry in Alon-Roichman graphs. Available as eprint http:\/\/arxiv.org\/abs\/1009.5695v1arXiv:1009.5695v1."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000757"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748073"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806776"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090776"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873657"},{"key":"e_1_2_1_55_1","unstructured":"David Steurer. 2010c. Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion. Manuscript available from the author's website. http:\/\/www.cs.cornell.edu\/∼dsteurer\/. David Steurer. 2010c. Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion. Manuscript available from the author's website. http:\/\/www.cs.cornell.edu\/∼dsteurer\/."},{"key":"e_1_2_1_56_1","unstructured":"David Steurer. 2014. Subexponential approximations for multicut. Manuscript available from the author's website. http:\/\/www.cs.cornell.edu\/∼dsteurer\/. David Steurer. 2014. Subexponential approximations for multicut. Manuscript available from the author's website. http:\/\/www.cs.cornell.edu\/∼dsteurer\/."},{"key":"e_1_2_1_58_1","volume-title":"Orsay","author":"Szemer\u00e9di E.","year":"1976","unstructured":"E. Szemer\u00e9di . 1976. Regular partitions of graphs. Probl\u00e8mes combinatoires et th\u00e9orie des graphes , Orsay ( 1976 ). E. Szemer\u00e9di. 1976. Regular partitions of graphs. Probl\u00e8mes combinatoires et th\u00e9orie des graphes, Orsay (1976)."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.22"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2775105","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2775105","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:39Z","timestamp":1750231179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2775105"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":56,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2775105"],"URL":"https:\/\/doi.org\/10.1145\/2775105","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}