{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004518,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":53,"publisher":"ACM","funder":[{"name":"NSF CAREER Award","award":["2047933"],"award-info":[{"award-number":["2047933"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718137","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"631-642","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Rounding Large Independent Sets on Expanders"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3003-2017","authenticated-orcid":false,"given":"Mitali","family":"Bafna","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8762-9658","authenticated-orcid":false,"given":"Jun-Ting","family":"Hsieh","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8689-6770","authenticated-orcid":false,"given":"Pravesh K.","family":"Kothari","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132537"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794270248"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3114207.3114755"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.59"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_1_6_1","volume-title":"New Approximation Guarantee for Chromatic Number. In 38th Annual ACM Symposium on Theory of Computing, STOC\u201906","author":"Arora Sanjeev","year":"2006","unstructured":"Sanjeev Arora, Eden Chlamtac, and Moses Charikar. 2006. New Approximation Guarantee for Chromatic Number. In 38th Annual ACM Symposium on Theory of Computing, STOC\u201906. 215\u2013224."},{"key":"e_1_3_2_1_7_1","volume-title":"New Tools for Graph Coloring. In International Workshop on Approximation Algorithms for Combinatorial Optimization. 1\u201312","author":"Arora Sanjeev","year":"2011","unstructured":"Sanjeev Arora and Rong Ge. 2011. New Tools for Graph Coloring. In International Workshop on Approximation Algorithms for Combinatorial Optimization. 1\u201312."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374380"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451099"},{"key":"e_1_3_2_1_10_1","volume-title":"39th Computational Complexity Conference.","author":"Bafna Mitali","year":"2024","unstructured":"Mitali Bafna and Dor Minzer. 2024. Solving Unique Games over Globally Hypercontractive Graphs. In 39th Computational Complexity Conference."},{"key":"e_1_3_2_1_11_1","volume-title":"Optimal Long Code Test with One Free Bit. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 453\u2013462","author":"Bansal Nikhil","year":"2009","unstructured":"Nikhil Bansal and Subhash Khot. 2009. Optimal Long Code Test with One Free Bit. In 2009 50th Annual IEEE Symposium on Foundations of Computer Science. 453\u2013462."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055488"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_2_1_14_1","unstructured":"Boaz Barak and David Steurer. 2016. Proofs beliefs and algorithms through the lens of sum-of-squares. Course notes: http:\/\/www.sumofsquares.org\/public\/index.html"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2404.14159"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/176584.176586"},{"key":"e_1_3_2_1_17_1","volume-title":"Information processing letters, 61, 1","author":"Blum Avrim","year":"1997","unstructured":"Avrim Blum and David Karger. 1997. An ~ O(n^3\/14)-coloring algorithm for 3-colorable graphs. Information processing letters, 61, 1 (1997), 49\u201353."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1034"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01994876"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585184"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055491"},{"volume-title":"Non-local analysis of SDP-based approximation algorithms","author":"Chlamtac Eden","key":"e_1_3_2_1_22_1","unstructured":"Eden Chlamtac. 2009. Non-local analysis of SDP-based approximation algorithms. Princeton University."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897561"},{"key":"e_1_3_2_1_24_1","volume-title":"36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS","author":"Deshpande Amit","year":"2016","unstructured":"Amit Deshpande, Prahladh Harsha, and Rakesh Venkat. 2016. Embedding Approximately Low-Dimensional \u2113 _2^2 Metrics into \u2113 _1. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.84"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132567"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548010240415X"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1773"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781680836370"},{"key":"e_1_3_2_1_31_1","first-page":"2353","article-title":"Limits of local algorithms over sparse random graphs","volume":"45","author":"Gamarnik David","year":"2017","unstructured":"David Gamarnik and Madhu Sudan. 2017. Limits of local algorithms over sparse random graphs. Annals of probability: An official journal of the Institute of Mathematical Statistics, 45, 4 (2017), 2353\u20132376.","journal-title":"Annals of probability: An official journal of the Institute of Mathematical Statistics"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2020.62"},{"volume-title":"Graph Theory and its Applications. Acad","author":"Hoffman Alan J","key":"e_1_3_2_1_33_1","unstructured":"Alan J Hoffman. 1970. On eigenvalues and colorings of graphs. In Graph Theory and its Applications. Acad. Press, 79\u201391."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030402"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"volume-title":"Reducibility among combinatorial problems","author":"Karp Richard M","key":"e_1_3_2_1_36_1","unstructured":"Richard M Karp. 1972. Reducibility among combinatorial problems. Springer."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3001582","article-title":"Coloring 3-Colorable Graphs with Less than n^1\/5 Colors","volume":"64","author":"Mikkel Thorup Kawarabayashi","year":"2017","unstructured":"Ken-ichi Kawarabayashi and Mikkel Thorup. 2017. Coloring 3-Colorable Graphs with Less than n^1\/5 Colors. Journal of the ACM (JACM), 64, 1 (2017), 1\u201323.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC","author":"Thorup Mikkel","year":"2024","unstructured":"Ken-ichi Kawarabayashi, Mikkel Thorup, and Hirotaka Yoneda. 2024. Better Coloring of 3-Colorable Graphs. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024). Association for Computing Machinery, New York, NY, USA. 331\u2013339. isbn:9798400703836"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.75"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"e_1_3_2_1_42_1","volume-title":"Finding Pseudorandom Colorings of Pseudorandom Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS","author":"Kumar Akash","year":"2018","unstructured":"Akash Kumar, Anand Louis, and Madhur Tulsiani. 2018. Finding Pseudorandom Colorings of Pseudorandom Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400366802"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18318-8_17"},{"key":"e_1_3_2_1_45_1","volume-title":"44th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Manurangsi Pasin","year":"2017","unstructured":"Pasin Manurangsi and Prasad Raghavendra. 2017. A Birthday Repetition Theorem and Complexity of Approximating Dense CSPs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.45"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.94.197205"},{"volume-title":"Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation","author":"Parrilo Pablo A.","key":"e_1_3_2_1_48_1","unstructured":"Pablo A. Parrilo. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph. D. Dissertation. California Institute of Technology."},{"key":"e_1_3_2_1_49_1","unstructured":"Yuval Rabani and Rakesh Venkat. 2017. Approximating Sparsest Cut in Low Rank Graphs via Embeddings from Approximately Low Dimensional Spaces. Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.33"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a005"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2157.2158"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2405.20368"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718137","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:40:00Z","timestamp":1750693200000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":53,"alternative-id":["10.1145\/3717823.3718137","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718137","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}