Tight Sum-of-squares Lower Bounds for Binary Polynomial Optimization Problems

For binary polynomial optimization problems of degree 2d with n variables Sakaue, Takeda, Kim, and Ito [33] proved that the
th semidefinite (SDP) relaxation in the SoS/Lasserre hierarchy of SDP relaxations provides the exact optimal value. When n is an odd number, we show that their analysis is tight, i.e., we prove that
levels of the SoS/Lasserre hierarchy are also necessary.
Laurent [24] showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull of a linear representation of a set with no integral points. She conjectured that the SoS/Lasserre rank for the same problem is n-1. In this article, we disprove this conjecture and derive lower and upper bounds for the rank.