2026-07-21T23:53:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10655 2024-03-06T10:46:23Z ddc:004 open_access

Sum-Of-Squares Bounds via Boolean Function Analysis Kurpisz, Adam SoS certificate SoS rank hypercube optimization semidefinite programming We introduce a method for proving bounds on the SoS rank based on Boolean Function Analysis and Approximation Theory. We apply our technique to improve upon existing results, thus making progress towards answering several open questions. We consider two questions by Laurent. First, finding what is the SoS rank of the linear representation of the set with no integral points. We prove that the SoS rank is between ceil[n/2] and ceil[~ n/2 +sqrt{n log{2n}} ~]. Second, proving the bounds on the SoS rank for the instance of the Min Knapsack problem. We show that the SoS rank is at least Omega(sqrt{n}) and at most ceil[{n+ 4 ceil[sqrt{n} ~]}/2]. Finally, we consider the question by Bienstock regarding the instance of the Set Cover problem. For this problem we prove the SoS rank lower bound of Omega(sqrt{n}). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Kurpisz 2019 Is Part Of LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2019.79 urn:nbn:de:0030-drops-106556 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.79 eng https://creativecommons.org/licenses/by/3.0/legalcode