On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy

Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli

The Lasserre/Sum-of-Squares (SoS) hierarchy is a systematic procedure for constructing a sequence of increasingly tight semidefinite relaxations. It is known that the hierarchy con…