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 B ⁿ= { 0 , 1 } ⁿ. This hierarchy provides for each integer r∈ N a lower bound f _{( r )} on the minimum f _min of f, given by the largest scalar λ for which the polynomial f- λ is a sum-of-squares on B ⁿ 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∈ [0 , 1 / 2] , we can show that this worst-case error in the regime r≈ t· n is of the order 1/2-t(1-t) as n tends to ∞. Our proof combines classical Fourier analysis on B ⁿ 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 (Z/ qZ) ⁿ. Furthermore, our results apply to the setting of matrix-valued polynomials.