2026-07-26T21:31:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6336 2024-03-06T10:37:48Z ddc:004 open_access

Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems Kurpisz, Adam Leppänen, Samuli Mastrolilli, Monaldo SoS/Lasserre hierarchy lift and project methods binary polynomial optimization 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, we prove that (n+2d-1)/2 levels of the SoS/Lasserre hierarchy are necessary to provide the exact optimal value. This matches the recent upper bound result by Sakaue, Takeda, Kim and Ito. Additionally, we study a conjecture by Laurent, who considered the linear representation of a set with no integral points. She showed that the Sherali-Adams hierarchy requires n levels to detect the empty integer hull, and conjectured that the SoS/Lasserre rank for the same problem is n-1. We disprove this conjecture and derive lower and upper bounds for the rank. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Kurpisz and Samuli Leppänen and Monaldo Mastrolilli 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.78 urn:nbn:de:0030-drops-63368 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.78 eng https://creativecommons.org/licenses/by/3.0/legalcode