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) ⁿ.