SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization

We introduce several methods to study the rank of the sum of squares (SoS) hierarchy for problems over the Boolean hypercube. We apply our techniques to improve upon existing results, thus answering several open questions. We answer the question by Laurent regarding the SoS rank of the empty integral hull (EIH) problem. We prove that the SoS rank is between $\lceil \frac{n}{2}\rceil$ and $\lceil \frac{n}{2}+\sqrt{n\log 2n}\rceil$. We refute the Lee-Prakash-de Wolf-Yuen (LPdWY) conjecture for the SoS rank of symmetric quadratic functions in n variables with roots placed in points k – 1 and k that conjectured the lower bound of $\mathrm{\Omega }(n)$. We prove that the SoS rank for SQFs is at most $O(\sqrt{nk}\log (n))$. We answer another question by Laurent for an instance of the min knapsack problem parameterized by P. We prove a nearly tight SoS rank between $\mathrm{\Omega }(\sqrt{n\log P})$ and $O(\sqrt{n}\log P)$. Finally, we refute the conjecture by Bienstock-Zuckerberg that presumed the SoS rank lower bound of $n/4$ for an instance of the set cover problem. We refute the conjecture by providing an $O(\sqrt{n}\log (n))$ SoS certificate for this problem.

Funding: A. Kurpisz was supported by Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung (SNSF) [Grant PZ00P2_174117], A. Potechin was supported in part by the National Science Foundation (NSF) [Grant CCF2008920], and E. Wirth was supported by DFG under Germany’s Excellence Strategy, The Berlin Mathematics Research Center (MATH+) [Grant EXC-2046/1, project ID 390685689, BMS Stipend].