SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization

Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth

We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in $n$ variables with roots placed in points $k-1$ and $…