Local-Minima-Preserving Polynomial Relaxation of Ising Problems
Debraj Banerjee, Santanu Mahapatra, Kunal Narayan Chaudhury
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 that 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 scalable gradient-based optimizers such as ADAM. We demonstrate that our method achieves strong performance across challenging benchmarks, including spin-glass models, MAX-CUT, and NPP.
BibTeX
@inproceedings{
banerjee2026localminimapreserving,
title={Local-Minima-Preserving Polynomial Relaxation of Ising Problems},
author={Debraj Banerjee and Santanu Mahapatra and Kunal N. Chaudhury},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=EBTMJ3MXt0}
}