{"ID":5346758,"CreatedAt":"2026-06-30T04:09:55.830587294Z","UpdatedAt":"2026-07-02T14:12:34.668891255Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.30333","arxiv_id":"2606.30333","title":"Local-Minima-Preserving Continuous Relaxation of Ising Problems","abstract":"The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theorem: there exists a one-to-one correspondence between the local minima of the relaxation and the one-flip minima of the original Ising problem. This guarantee reduces the Ising problem to finding the local minima of a smooth function, allowing us to leverage gradient-based optimizers such as ADAM. We demonstrate that our method is scalable and it achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.","short_abstract":"The generalized Ising problem captures a broad spectrum of hard combinatorial problems, including MAX-CUT, Number Partitioning (NPP), and Maximum Independent Set. In this work, we consider the notion of one-flip local minima for this problem. We construct a polynomial relaxation and prove the landscape equivalence theo...","url_abs":"https://arxiv.org/abs/2606.30333","url_pdf":"https://arxiv.org/pdf/2606.30333v1","authors":"[\"Debraj Banerjee\",\"Santanu Mahapatra\",\"Kunal N. Chaudhury\"]","published":"2026-06-29T14:13:56Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.LG\",\"physics.comp-ph\"]","methods":"[]","has_code":false}