{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T12:30:15Z","timestamp":1787229015406,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-1763179"],"award-info":[{"award-number":["DMS-1763179"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Appl. Dyn. Syst."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We consider the Max-Cut problem. Let [Formula: see text] be a graph with adjacency matrix [Formula: see text]. Burer, Monteiro, and Zhang proposed to find, for [Formula: see text] angles [Formula: see text], minima of the energy [Formula: see text]. Configurations achieving a global minimum leads to a partition of size at least [Formula: see text]. This approach is known to be computationally viable and leads to very good results in practice. We prove, for each [Formula: see text], that replacing [Formula: see text] with an explicit [Formula: see text] global minima lead to a partition of size at least [Formula: see text]. This suggests some interesting algorithms that perform well. It also shows that the problem of finding approximate global minima of energy functionals of this type is NP-hard, in general.<\/jats:p>","DOI":"10.1137\/21m1432211","type":"journal-article","created":{"date-parts":[[2023,5,31]],"date-time":"2023-05-31T16:17:17Z","timestamp":1685549837000},"page":"730-743","source":"Crossref","is-referenced-by-count":5,"title":["Max-Cut via Kuramoto-Type Oscillators"],"prefix":"10.1137","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7745-4217","authenticated-orcid":true,"given":"Stefan","family":"Steinerberger","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of Washington, Seattle, WA 98195-4350 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,5,31]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"ref2","unstructured":"N. Boumal , \nV. Voroninski , and \nA. Bandeira , The non-convex Burer-Monteiro approach works on smooth semidefinite programs, in Proceedings of the 30th International Conference on Neural Information Processing Systems, 2016, pp. 2765\u20132773."},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21830"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-002-0352-8"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0564-1"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623400382467"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-019-49699-5"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2014.04.012"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1212134110"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2017.0798"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"ref12","doi-asserted-by":"crossref","unstructured":"J. Hastad , Some optimal inapproximability results, in Proceedings of the 29th ACM Symposium on Theory of Computing, El Paso, TX, ACM, 1997, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"M. Kassabov , \nS. Strogatz , and \nA. Townsend , Sufficiently Dense Kuramoto Networks are Globally Synchronizing, preprint, arXiv:2105.11406, 2021.","DOI":"10.1063\/5.0057659"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447372"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"Y. Kuramoto , Self-entrainment of a population of coupled non-linear oscillators, in Proceedings of the International Symposium on Mathematical Problems in Theoretical Physics, Lecture Notes in Phys. 39, Springer, Berlin, pp. 420\u2013422.","DOI":"10.1007\/BFb0013365"},{"key":"ref16","unstructured":"S. Ling , Solving Orthogonal Group Synchronization via Convex and Low-Rank Optimization: Tightness and Landscape Analysis, preprint, arXiv:2006.00902, 2020."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/18M1217644"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1088\/1361-6544\/ab9baa"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-020-18445-1"},{"key":"ref20","unstructured":"S. Steinerberger , A Graph Decomposition Motivated by the Geometry of Randomized Rounding, preprint, arXiv:2104.11198, 2021."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/45\/5\/055102"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"A. Townsend , \nM. Stillman , and \nS. H. Strogatz , Circulant Networks of Identical Kuramoto Oscillators: Seeking Dense Networks That Do Not Globally Synchronize and Sparse Ones That Do, preprint, arXiv:1906.10627v1, 2019.","DOI":"10.1063\/5.0018322"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"L. Trevisan , \nG. Sorkin , \nM. Sudan , and \nD. Williamson , Gadgets, approximation, and linear programming, in Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2000, pp. 617\u2013626.","DOI":"10.1109\/SFCS.1996.548521"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"T. Wang  and \nJ. Roychowdhury , OIM: Oscillator-based Ising machines for solving combinatorial optimisation problems, in Proceedings of the 18th International Conference on Unconventional Computation and Natural Computation, UCNC, pp. 232\u2013256.","DOI":"10.1007\/978-3-030-19311-9_19"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"T. Wang , \nL. Wu , and \nJ. Roychowdhury , New computational results and hardware prototypes for oscillator-based Ising machines, in Proceedings of the 561th Annual Design Automation Conference, 2019, 239.","DOI":"10.1145\/3316781.3322473"}],"container-title":["SIAM Journal on Applied Dynamical Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/21M1432211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,20]],"date-time":"2026-08-20T12:15:01Z","timestamp":1787228101000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/21M1432211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,31]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/21M1432211"],"URL":"https:\/\/doi.org\/10.1137\/21m1432211","relation":{},"ISSN":["1536-0040"],"issn-type":[{"value":"1536-0040","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,31]]}}}