Kurpisz, Adam AndrzejAdam AndrzejKurpiszLeppänen, SamuliSamuliLeppänenMastrolilli, MonaldoMonaldoMastrolilli2025-04-292025-04-292015-10-07https://arbor.bfh.ch/handle/arbor/450751510.01891v1The 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 converges to the 0/1 polytope in n levels and captures the convex relaxations used in the best available approximation algorithms for a wide variety of optimization problems. In this paper we characterize the set of 0/1 integer linear problems and unconstrained 0/1 polynomial optimization problems that can still have an integrality gap at level n-1. These problems are the hardest for the Lasserre hierarchy in this sense.encs.CCcs.DSconference_item