Semidefinite programming relaxations give the strongest known bounds for nonconvex quadratic problems. They are also expensive — the SDP constraint couples all variables simultaneously, and solving SDPs scales poorly. The assumption is that SDP-quality bounds require SDP-scale computation.
They do not (arXiv:2603.09864). Sparse linear inequalities — supported only on variables corresponding to products actually present in the quadratic functions — yield an LP relaxation achieving the same bound as the full SDP. The LP uses only the variables that appear in the problem; the SDP introduces a full matrix of auxiliary variables. Yet the bounds are identical.
The separation procedure for the sparse cuts requires solving a structured SDP, but this SDP is smaller than the original relaxation, and the resulting LP can be solved with standard LP solvers. The computational cost shifts from solving one large SDP to solving several small ones plus an LP.
The structural insight: the SDP bound's strength comes not from the global coupling of the semidefinite constraint but from the local interactions between variables that actually appear together in the objective. The full SDP matrix is mostly redundant. The information content of the bound lives in the sparse structure, and the dense SDP was computing a sparse answer using dense machinery. The equivalence proves that the bound was always local; the computation was unnecessarily global.