{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:46:47Z","timestamp":1782737207553,"version":"3.54.5"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF:2008920"],"award-info":[{"award-number":["CCF:2008920"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ISF","award":["2735\/2025"],"award-info":[{"award-number":["2735\/2025"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>Assuming the unique games conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the max cut problem is [Formula: see text], obtained by the celebrated SDP-based approximation algorithm of Goemans and Williamson. The current best approximation algorithm for max di-cut, i.e., the max cut problem in directed graphs, achieves a ratio of about 0.87401, leaving open the question of whether max di-cut can be approximated as well as max cut. We obtain a slightly improved algorithm for max di-cut and a new UGC-hardness for it, showing that [Formula: see text], where [Formula: see text] is the best approximation ratio that can be obtained in polynomial time for max di-cut under UGC. Our new upper bound shows that max di-cut cannot be approximated as well as max cut, which separates max di-cut from max cut and resolves a question raised by Feige and Goemans. A natural generalization of max di-cut is the max [Formula: see text]-and problem in which each constraint is of the form [Formula: see text], where [Formula: see text] and [Formula: see text] are literals, i.e., variables or their negations (in max di-cut each constraint is of the form [Formula: see text] where [Formula: see text] and [Formula: see text] are variables).\u00a0Austrin separated max [Formula: see text]-and from max cut by showing that [Formula: see text] and conjectured that max [Formula: see text]-and and max di-cut have the same approximation ratio. Our new lower bound on max di-cut refutes this conjecture, completing the separation of the three problems max [Formula: see text]-and, max di-cut, and max cut. We also obtain a new lower bound for max [Formula: see text]-and, showing that [Formula: see text]. Our upper bound on max di-cut is achieved via a simple, analytical proof. The new lower bounds on max di-cut and max [Formula: see text]-and, i.e., the new approximation algorithms, use experimentally discovered distributions of rounding functions which are then verified via computer-assisted proofs. Code for the project is available at https:\/\/github.com\/jbrakensiek\/max-dicut .<\/jats:p>","DOI":"10.1137\/24m1635776","type":"journal-article","created":{"date-parts":[[2026,5,28]],"date-time":"2026-05-28T07:25:28Z","timestamp":1779953128000},"page":"FOCS23-268-FOCS23-308","source":"Crossref","is-referenced-by-count":0,"title":["Separating MAX 2-AND, MAX DI-CUT, and MAX CUT"],"prefix":"10.1137","volume":"55","author":[{"given":"Joshua","family":"Brakensiek","sequence":"first","affiliation":[{"name":"Department of Electrical Engineering and Computer Sciences, University of California, Berkeley, CA 94720 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5669-2646","authenticated-orcid":true,"given":"Neng","family":"Huang","sequence":"additional","affiliation":[{"name":"Computer Science and Engineering Division, University of Michigan, Ann Arbor, MI 48109 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-8205-1608","authenticated-orcid":true,"given":"Aaron","family":"Potechin","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Chicago, Chicago, IL 60637 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7638-7710","authenticated-orcid":true,"given":"Uri","family":"Zwick","sequence":"additional","affiliation":[{"name":"Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,5,28]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1145\/3459096"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1080\/23307706.2017.1397554"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00021-0"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1202"},{"key":"ref6","doi-asserted-by":"crossref","unstructured":"P. Austrin, Balanced MAX 2-SAT might not be the hardest, in Proceedings of the 39th STOC, 2007, pp. 189\u2013197.","DOI":"10.1145\/1250790.1250818"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1137\/070711670"},{"key":"ref8","series-title":"Lecture Notes in Comput. Sci. 3879","first-page":"27","volume-title":"Approximation and Online Algorithms","author":"Avidor A.","year":"2005"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1137\/23M1591578"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"J. Brakensiek, N. Huang, and U. Zwick, Tight approximability of max 2-sat and relatives, under UGC, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2024, pp. 1328\u20131344, https:\/\/doi.org\/10.1137\/1.9781611977912.5.","DOI":"10.1137\/1.9781611977912.53"},{"key":"ref11","volume-title":"Some Notes on Computation of Games Solutions","author":"Brown G. W.","year":"1949"},{"key":"ref12","volume-title":"Lecture notes","author":"Daskalakis C.","year":"2011"},{"key":"ref13","first-page":"1","volume":"17","author":"Diamond S.","year":"2016","journal-title":"J. Mach. Learn. Res."},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"A. Domahidi, E. Chu, and S. Boyd, ECOS:\u00a0An SOCP solver for embedded systems, in Proceedings of theEuropean Control Conference (ECC), IEEE, 2013, pp. 3071\u20133076.","DOI":"10.23919\/ECC.2013.6669541"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1080\/00949659008811236"},{"key":"ref16","unstructured":"R. Eldan and A. Naor, Krivine Diffusions Attain the Goemans\u2013Williamson Approximation Ratio, https:\/\/arxiv.org\/abs\/1906.10615, 2019."},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"U. Feige and M. Goemans, Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT, in Proceedings of the Third Israel Symposium on the Theory of Computing and Systems, IEEE, 1995, pp. 182\u2013189.","DOI":"10.1109\/ISTCS.1995.377033"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.1992.10477010"},{"key":"ref19","first-page":"400","volume":"25","author":"Genz A.","year":"1993","journal-title":"Comput. Sci. Statist."},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1023\/B:STCO.0000035304.20635.31"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1145\/3422622"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1162"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2007.55"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2017.2690633"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96418-8_30"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1145\/3328732"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"H. Karloff and U. Zwick, A 7\/8-approximation algorithm for MAX 3SAT? in Proceedings of the of 38th FOCS, IEEE, 1997, pp. 406\u2013415.","DOI":"10.1109\/SFCS.1997.646129"},{"key":"ref30","first-page":"767","volume-title":"Proceedings of FOCS","author":"Khot S.","year":"2002"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"M. Lewin, D. Livnat, and U. Zwick, Improved rounding techniques for the MAX.\u00a02-SAT and MAX DI-CUT problems, in Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, Springer, New York, 2002, pp. 67\u201382.","DOI":"10.1007\/3-540-47867-1_6"},{"key":"ref33","first-page":"287","volume-title":"The Constraint Satisfaction Problem:\u00a0Complexity and Approximability, Dagstuhl Follow-Ups 7","author":"Makarychev K.","year":"2017"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.15807\/jorsj.46.178"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.2307\/1969529"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448847"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"ref38","doi-asserted-by":"crossref","unstructured":"P. Raghavendra, Optimal algorithms and inapproximability results for every CSP? in Proceedings of the 40th STOC, 2008, pp. 245\u2013254.","DOI":"10.1145\/1374376.1374414"},{"key":"ref39","unstructured":"P. Raghavendra, Approximating NP-hard Problems\u2014Efficient Algorithms and their Limits, Ph.D. thesis, University of Washington, 2009."},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"P. Raghavendra and D. Steurer, How to round any CSP, in Proceedings of the 50th FOCS, IEEE, 2009, pp. 586\u2013594.","DOI":"10.1109\/FOCS.2009.74"},{"key":"ref41","first-page":"42","volume":"36","author":"Tange O.","year":"2011","journal-title":"USENIX Magazine"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797328847"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1038\/s41592-019-0686-2"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2002.07.001"},{"key":"ref45","unstructured":"U. Zwick, Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint, in Proceedings of the 9th SODA, 1998, pp. 201\u2013210."},{"key":"ref46","first-page":"679","author":"Zwick U.","year":"1999","journal-title":"Proceedings of the 31st STOC, ACM"},{"key":"ref47","unstructured":"U. Zwick, Computer assisted proof of optimal approximability results, in Proceedings of the 13th SODA, 2002, pp. 496\u2013505."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,29]],"date-time":"2026-06-29T12:15:37Z","timestamp":1782735337000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1635776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,28]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/24M1635776"],"URL":"https:\/\/doi.org\/10.1137\/24m1635776","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,28]]}}}