{"id":"arxiv/2605.00594","url":"https://arxiv.org/abs/2605.00594","tags":["math.OC","cs.CC","cs.DS"],"score":0,"title":"On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank","domain":"math.OC","source":"arxiv","authors":["Adam Kurpisz","Lucas Slot","Mikhail Zaytsev"],"reviews":0,"subject":"math.OC","summary":"We analyze the sum-of-squares rank of unweighted instances of the Minimum Knapsack (MK) problem, i.e., minimization of $\\sum_{i=1}^n x_i$ for 0/1 variables under the constraint $\\sum_{i=1}^n x_i \\geq q$, with $q \\in \\mathbb{R}$. Such instances have long served as a testbed for understanding the limitations of lift-and-project methods in Boolean optimization. For example, both the Lovász-Schrijver and Sherali-Adams hierarchies require (maximal) rank $n$ to solve them, already when $q=1/2$ is constant. The SOS hierarchy requires only \\emph{sublinear} rank $O(\\sqrt{n})$ to solve unweighted MK…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-01","reactions":{}}