Certified computational study of the gap shape of degree-4 sum-of-squares relaxations of unique games. A null result on the main question, two proved theorems on Paley graphs, and a structural determination of the degree-4 extension. Fully reproducible: 132 checks, 0 mismatches.
reproducible-research theoretical-computer-science semidefinite-programming computational-complexity sum-of-squares polynomial-optimization approximation-algorithms max-cut cayley-graphs negative-results unique-games-conjecture certified-computation integrality-gap lasserre-hierarchy paley-graphs
-
Updated
Sep 18, 2026 - Python