{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,24]],"date-time":"2025-09-24T10:30:19Z","timestamp":1758709819291,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC Discovery","award":["RGPIN-2016-06333"],"award-info":[{"award-number":["RGPIN-2016-06333"]}]},{"name":"NWO VICI","award":["639.023.812"],"award-info":[{"award-number":["639.023.812"]}]},{"name":"NSF","award":["CCF-BSF:AF1717947, and CCF-1740425"],"award-info":[{"award-number":["CCF-BSF:AF1717947, and CCF-1740425"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            Semidefinite programming is a powerful tool in the design and analysis of approximation algorithms for combinatorial optimization problems. In particular, the random hyperplane rounding method of Goemans and Williamson [\n            <jats:xref ref-type=\"bibr\">31<\/jats:xref>\n            ] has been extensively studied for more than two decades, resulting in various extensions to the original technique and beautiful algorithms for a wide range of applications. Despite the fact that this approach yields tight approximation guarantees for some problems, e.g.,\n            <jats:sc>Max-Cut<\/jats:sc>\n            , for many others, e.g.,\n            <jats:sc>Max-SAT<\/jats:sc>\n            and\n            <jats:sc>Max-DiCut<\/jats:sc>\n            , the tight approximation ratio is still unknown. One of the main reasons for this is the fact that very few techniques for rounding semi-definite relaxations are known.\n          <\/jats:p>\n          <jats:p>\n            In this work, we present a new general and simple method for rounding semi-definite programs, based on Brownian motion. Our approach is inspired by recent results in algorithmic discrepancy theory. We develop and present tools for analyzing our new rounding algorithms, utilizing mathematical machinery from the theory of Brownian motion, complex analysis, and partial differential equations. Focusing on constraint satisfaction problems, we apply our method to several classical problems, including\n            <jats:sc>Max-Cut<\/jats:sc>\n            ,\n            <jats:sc>Max-2SAT<\/jats:sc>\n            , and\n            <jats:sc>Max-DiCut<\/jats:sc>\n            , and derive new algorithms that are competitive with the best known results. To illustrate the versatility and general applicability of our approach, we give new approximation algorithms for the\n            <jats:sc>Max-Cut<\/jats:sc>\n            problem with side constraints that crucially utilizes measure concentration results for the Sticky Brownian Motion, a feature missing from hyperplane rounding and its generalizations.\n          <\/jats:p>","DOI":"10.1145\/3459096","type":"journal-article","created":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T17:55:44Z","timestamp":1644602144000},"page":"1-50","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Sticky Brownian Rounding and its Applications to Constraint Satisfaction Problems"],"prefix":"10.1145","volume":"18","author":[{"given":"Sepehr","family":"Abbasi-Zadeh","sequence":"first","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Nikhil","family":"Bansal","sequence":"additional","affiliation":[{"name":"TU Eindhoven, and Centrum Wiskunde &amp; Informatica, Amsterdam, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0963-3843","authenticated-orcid":false,"given":"Guru","family":"Guruganesh","sequence":"additional","affiliation":[{"name":"Google Research, CA, USA"}]},{"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, ON, Canada"}]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[{"name":"Technion, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0827-233X","authenticated-orcid":false,"given":"Mohit","family":"Singh","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_4_2_2","unstructured":"Sepehr Abbasi-Zadeh Nikhil Bansal Guru Guruganesh Aleksandar Nikolov Roy Schwartz and Mohit Singh. 2018. Code for PDE Solvability and Sum of Square Proofs. Retrieved from https:\/\/github.com\/sabbasizadeh\/brownian-rounding."},{"key":"e_1_3_4_3_2","volume-title":"Complex Analysis: An Introduction to the Theory of Analytic Functions of One Complex Variable (second ed.)","author":"Ahlfors Lars V.","year":"1966","unstructured":"Lars V. Ahlfors. 1966. Complex Analysis: An Introduction to the Theory of Analytic Functions of One Complex Variable (second ed.). McGraw-Hill Book Company."},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441629"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107325937"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132548"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.030"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1202"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250818"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958048"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2907052"},{"key":"e_1_3_4_13_2","first-page":"24:1\u201324:17","volume-title":"Proceedings of the APPROX-RANDOM (LIPIcs)","author":"Austrin Per","year":"2019","unstructured":"Per Austrin and Aleksa Stankovic. 2019. Global cardinality constraints make approximating some Max-2-CSPs harder. In Proceedings of the APPROX-RANDOM (LIPIcs). 24:1\u201324:17."},{"key":"e_1_3_4_14_2","first-page":"27","volume-title":"Proceedings of the Workshop on Approximation and Online Algorithms","author":"Avidor Adi","year":"2005","unstructured":"Adi Avidor, Ido Berkovitch, and Uri Zwick. 2005. Improved approximation algorithms for Max NAE-SAT and Max SAT. In Proceedings of the Workshop on Approximation and Online Algorithms. 27\u201340."},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.7"},{"key":"e_1_3_4_16_2","first-page":"788","volume-title":"Foundations of Computer Science FOCS","author":"Bansal Nikhil","year":"2016","unstructured":"Nikhil Bansal, Daniel Dadush, and Shashwat Garg. 2016. An algorithm for Koml\u00f3s conjecture matching Banaszczyk\u2019s bound. In Foundations of Computer Science FOCS. 788\u2013799."},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188850"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.95"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511762543"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-012-0161-z"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00190-1"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.124"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.39"},{"key":"e_1_3_4_25_2","unstructured":"Ronen Eldan and Assaf Naor. 2019. Krivine diffusions attain the Goemans-Williamson approximation ratio. arxiv:1906.10615. Retrieved from http:\/\/arxiv.org\/abs\/1906.10615."},{"key":"e_1_3_4_26_2","unstructured":"Uriel Feige and Michel Goemans. 1995. Approximating the value of two power proof systems with applications to Max 2-SAT and Max DiCut. In Proceedings 3rd Israel Symposium on the Theory of Computing and Systems . IEEE 0182."},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_18"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523688"},{"key":"e_1_3_4_29_2","volume-title":"Elliptic Partial Differential Equations of Second Order","author":"Gilbarg David","year":"2015","unstructured":"David Gilbarg and Neil S. Trudinger. 2015. Elliptic Partial Differential Equations of Second Order. Springer."},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-4149(99)00109-X"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/3029311"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.36"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48777-8_16"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10035"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/274787.274791"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646129"},{"key":"e_1_3_4_39_2","first-page":"767","volume-title":"Proceedings of the Symposium on Theory of Computing","author":"Khot Subhash","year":"2002","unstructured":"Subhash Khot. 2002. On the power of unique 2-prover 1-round games. In Proceedings of the Symposium on Theory of Computing. 767\u2013775."},{"key":"e_1_3_4_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-47867-1_6"},{"key":"e_1_3_4_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/130929400"},{"key":"e_1_3_4_43_2","article-title":"0.935-approximation randomized algorithm for Max 2-SAT and its derandomization","author":"Matsui Tomomi","year":"2001","unstructured":"Tomomi Matsui and Shiro Matuura. 2001. 0.935-approximation randomized algorithm for Max 2-SAT and its derandomization. Department of Mathematical Engineering and Information Physics, University of Tokyo (Technical Report METR 2001-03) (2001).","journal-title":"Department of Mathematical Engineering and Information Physics, University of Tokyo (Technical Report METR 2001-03)"},{"key":"e_1_3_4_44_2","volume-title":"Brownian Motion","author":"M\u00f6rters Peter","year":"2010","unstructured":"Peter M\u00f6rters and Yuval Peres. 2010. Brownian Motion. Cambridge Series in Statistical and Probabilistic Mathematics."},{"key":"e_1_3_4_45_2","first-page":"21","volume-title":"Proceedings of the Foundations of Computer Science","author":"Mossel Elchanan","year":"2005","unstructured":"Elchanan Mossel, Ryan O\u2019Donnell, and Krzysztof Oleszkiewicz. 2005. Noise stability of functions with low influences: Invariance and optimality. In Proceedings of the Foundations of Computer Science. 21\u201330."},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556789808805690"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374425"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03185-8"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.74"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.33"},{"key":"e_1_3_4_52_2","first-page":"526","volume-title":"Proceedings of the Symposium on Discrete Algorithms","author":"Swamy Chaitanya","year":"2004","unstructured":"Chaitanya Swamy. 2004. Correlation clustering: Maximizing agreements via semidefinite programming. In Proceedings of the Symposium on Discrete Algorithms. 526\u2013527."},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1002\/sapm192321131"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011415"},{"key":"e_1_3_4_55_2","first-page":"201","volume-title":"Proceedings of the Symposium on Discrete Algorithms","author":"Zwick Uri","year":"1998","unstructured":"Uri Zwick. 1998. Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint. In Proceedings of the Symposium on Discrete Algorithms. 201\u2013210."},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301431"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459096","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459096","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459096","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:02Z","timestamp":1750193222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459096"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3459096"],"URL":"https:\/\/doi.org\/10.1145\/3459096","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2020-01-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}