Tight Sum-of-Squares lower bounds for binary polynomial optimization problems

Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli

We give two results concerning the power of the Sum-of-Squares(SoS)/Lasserre hierarchy. For binary polynomial optimization problems of degree $2d$ and an odd number of variables $n…