Sum-of-squares hierarchies for binary polynomial optimization

We consider the sum-of-squares hierarchy of approximations for the problem of minimizing a polynomial f over the boolean hypercube ${\mathbb{B}}^n={\{0,1\}}^n$. This hierarchy provides for each integer $r\in \mathbb{N}$ a lower bound $f_{(r)}$ on the minimum $f_{min}$ of f, given by the largest scalar $\lambda$ for which the polynomial $f-\lambda$ is a sum-of-squares on ${\mathbb{B}}^n$ with degree at most 2r. We analyze the quality of these bounds by estimating the worst-case error $f_{min}-f_{(r)}$ in terms of the least roots of the Krawtchouk polynomials. As a consequence, for fixed $t\in [0,1/2]$, we can show that this worst-case error in the regime $r\approx t·n$ is of the order $1/2-\sqrt{t(1-t)}$ as n tends to $\infty$. Our proof combines classical Fourier analysis on ${\mathbb{B}}^n$ with the polynomial kernel technique and existing results on the extremal roots of Krawtchouk polynomials. This link to roots of orthogonal polynomials relies on a connection between the hierarchy of lower bounds $f_{(r)}$ and another hierarchy of upper bounds $f^{(r)}$, for which we are also able to establish the same error analysis. Our analysis extends to the minimization of a polynomial over the q-ary cube ${(\mathbb{Z}/q\mathbb{Z})}^n$. Furthermore, our results apply to the setting of matrix-valued polynomials.