This record has been edited as far as possible, missing data will be added when the version of record is issued.
SoS Certification for Symmetric Quadratic Functions and Its Connection to Constrained Boolean Hypercube Optimization
METADATA ONLY
Loading...
Author / Producer
Date
2025
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
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 [$\frac{n}{2}$] and [$\frac{n}{2}$ + $\sqrt{n\ log\ 2n}$ ]. 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 $\Omega$(n). We prove that 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 $\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 certifin cate for this problem.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
Pages / Article No.
Publisher
INFORMS
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
sum of squares method; Boolean hypercube optimization; symmetric quadratic functions
Organisational unit
Notes
Funding
174117 - Theory and Applications of Linear and Semidefinite Relaxations for Combinatorial Optimization Problems (SNF)
Related publications and datasets
References: