pith. sign in

arxiv: 2605.00594 · v1 · submitted 2026-05-01 · 🧮 math.OC · cs.CC· cs.DS

On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank

Adam Kurpisz , Lucas Slot , Mikhail Zaytsev This is my paper

Pith reviewed 2026-05-09 19:04 UTC · model grok-4.3

classification 🧮 math.OC cs.CCcs.DS
keywords sum-of-squares hierarchyminimum knapsacksmoothed analysisSOS ranklift-and-project methodsboolean optimizationunweighted knapsackthreshold perturbation
0
0 comments X

The pith

Perturbing the knapsack threshold q with small Gaussian noise yields expected SOS rank O(sqrt(n) log(n/sigma)) for unweighted minimum knapsack.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies how the sum-of-squares rank of unweighted minimum knapsack varies with the threshold parameter q in the constraint sum x_i >= q. It establishes precise upper and lower bounds showing that linear rank occurs only for very specific small q, while constant rank suffices near q = n. The central result uses smoothed analysis to prove that random Gaussian perturbations make instances requiring linear rank rare, with the expected rank bounded by O(sqrt(n) log(n/sigma)). This matters because unweighted knapsack has served as a standard test case where other lift-and-project methods need full rank n even for constant q, so the typical behavior under perturbation clarifies when SOS hierarchies succeed in practice.

Core claim

For unweighted minimum knapsack, the SOS rank is constant when n-q is O(1). When q is O(1), linear rank is required precisely when q is exponentially close to an integer. As the main result, when q is perturbed by a Gaussian of mean zero and variance sigma squared, the expected SOS rank over the range of small q is O(sqrt(n) log(n/sigma)).

What carries the argument

Smoothed analysis of the SOS rank of the polynomial formulation of the unweighted minimum knapsack constraint, under Gaussian perturbations of the threshold q.

If this is right

  • Constant-rank SOS solves unweighted MK exactly when the threshold lies within O(1) of n.
  • Linear SOS rank is necessary only for q that are exponentially close to an integer when q itself is O(1).
  • Sublinear rank holds in expectation for all small q after any Gaussian perturbation of variance sigma squared.
  • The contrast with Lovasz-Schrijver and Sherali-Adams, which require rank n even for constant q, is preserved under perturbation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • High-rank instances occupy a set of q of vanishing measure, so average-case analysis over q would likely show sublinear SOS rank.
  • The same perturbation technique could be applied to other combinatorial problems known to have worst-case high SOS rank, to locate the typical rank.
  • The result suggests that the measure-zero character of hard instances may explain why SOS relaxations succeed on noisy or real-world data even when worst-case bounds are poor.

Load-bearing premise

The analysis uses the standard polynomial inequality encoding of the unweighted knapsack constraint together with the usual definition of SOS rank, and models perturbations as Gaussian with the given variance.

What would settle it

Compute or bound the SOS rank explicitly for a grid of q values spaced at distance sigma around several small integers, then check whether the average rank exceeds O(sqrt(n) log(n/sigma)).

Figures

Figures reproduced from arXiv: 2605.00594 by Adam Kurpisz, Lucas Slot, Mikhail Zaytsev.

Figure 1
Figure 1. Figure 1: Interpolation geometry for the univariate view at source ↗
Figure 2
Figure 2. Figure 2: Geometric constraints on the univariate σ1 when q < ⌊n/2⌋. Constructing σ1. We impose the following constraints on σ1 1. σ1(x) > 1 qb for all 0 ≤ x ≤ ⌊q⌋, 2. σ1(x) ≤ x−⌈q⌉ 2 for all ⌈q⌉ ≤ x ≤ ⌈q⌉ + 1, 3. σ1(x) ≤ 1 2 for all ⌈q⌉ + 1 ≤ x ≤ n. Let Td be the Chebyshev polynomial of the first kind. Denote by r0 the smallest root of Td  x n−⌊q⌋ − 1  and define τ (x) := 1 8 Td  x − ⌈q⌉ + r0 n − ⌊q⌋ − 1 m and … view at source ↗
read the original abstract

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\'asz-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 when $q=1/2$. On the other hand, when $q$ is allowed to vary with~$n$, the SOS rank of the problem may become linear. Interestingly, this is known to happen both when $q$ is large, and when $q$ is very small ($0<q \leq 2^{-n}$). This raises the question of whether we should think of hard instances of unweighted MK as being typical for the SOS hierarchy, or as a consequence of very specific choices of the threshold parameter $q$. In this paper, we address this question by showing new upper and lower bounds on the SOS rank of unweighted MK in the whole regime of the parameter $q$. For $n-q \leq O(1)$, we show that the SOS rank is constant. In contrast, when $q \leq O(1)$, a linear rank is needed if $q$ is exponentially close to an integer. As our main positive result, we show that linear rank is very rare for $q \leq O(1)$. This can be expressed in the language of smoothed analysis: after perturbing $q$ by a Gaussian with mean $0$ and variance $\sigma^2$, the expected SOS rank of MK is $O(\sqrt{n} \log (n/\sigma))$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper analyzes the SOS rank of unweighted minimum knapsack instances (minimize sum x_i subject to sum x_i >= q) over 0/1 variables. It establishes regime-specific bounds: constant rank when n-q = O(1); linear rank when q <= O(1) only if q is exponentially close to an integer; and an explicit (at most linear) functional dependence of rank on dist(q, Z). The main result is a smoothed-analysis bound: after adding Gaussian noise of variance sigma^2 to q, the expected SOS rank is O(sqrt(n) log(n/sigma)).

Significance. If the bounds hold, the work clarifies the typical-case behavior of the SOS hierarchy on a classic testbed for lift-and-project methods, showing that linear-rank instances are rare under natural perturbations. The explicit rank-vs-distance function and its direct integration against the Gaussian density to obtain the expectation are strengths, as is the separation of the constant-rank regime from the small-q regime.

minor comments (2)
  1. [§2.2] §2.2: the definition of the polynomial formulation of the MK constraint could explicitly state the degree-1 monomials used for the SOS relaxation to avoid ambiguity with the standard 0/1 encoding.
  2. [§4] The constant hidden in the O(1) for the n-q regime is not numerically illustrated; a short table of rank values for n-q = 1,2,3 would help readers verify the claimed constancy.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful review of the manuscript and for recommending acceptance. The referee's summary correctly identifies the key regimes analyzed and the main smoothed-analysis result.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper derives explicit upper and lower bounds on SOS rank as a function of the distance from q to the nearest integer (constant rank for n-q = O(1), linear rank only when q is exponentially close to an integer for q = O(1)). The smoothed-analysis expectation O(√n log(n/σ)) is obtained by direct integration of this rank function against the Gaussian density; the log factor arises from standard tail bounds on the distance to the nearest integer. No parameter is fitted to data and then renamed as a prediction, no self-citation is load-bearing for the central claim, and the polynomial formulation and SOS-rank definition are the standard ones stated in the problem setup. The derivation therefore reduces to the stated assumptions and the explicit rank-vs-distance relation rather than to any tautological or self-referential step.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the established definition of SOS rank for polynomial optimization problems and standard properties of Gaussian perturbations; no free parameters, ad-hoc axioms, or new invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definition of sum-of-squares hierarchy rank for 0/1 polynomial optimization
    The paper invokes the usual SOS rank notion for the knapsack polynomial constraint without re-deriving it.

pith-pipeline@v0.9.0 · 5702 in / 1294 out tokens · 41200 ms · 2026-05-09T19:04:12.672910+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Spielman and Shang-Hua Teng , title =

    John Dunagan and Daniel A. Spielman and Shang-Hua Teng , title =. Mathematical Programming , volume =

    work page

  2. [2]

    Spielman and Shang-Hua Teng , title =

    Daniel A. Spielman and Shang-Hua Teng , title =. Journal of the ACM , volume =

    work page

  3. [3]

    Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016) , pages =

    Tengyu Ma and Jonathan Shi and David Steurer , title =. Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016) , pages =. 2016 , publisher =

    work page 2016

  4. [4]

    Boaz Barak and Fernando G. S. L. Brand. Hypercontractivity, sum-of-squares proofs, and their applications , booktitle =. 2012 , publisher =

    work page 2012

  5. [5]

    Kothari and Jacob Steinhardt and David Steurer , title =

    Pravesh K. Kothari and Jacob Steinhardt and David Steurer , title =. Proceedings of the 50th Annual ACM Symposium on Theory of Computing (STOC 2018) , pages =. 2018 , publisher =

    work page 2018

  6. [6]

    Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017) , pages =

    Prasad Raghavendra and Satish Rao and Tselil Schramm , title =. Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC 2017) , pages =. 2017 , publisher =

    work page 2017

  7. [7]

    Approximation, Randomization, and Combinatorial Optimization

    Vijay Bhattiprolu and Venkatesan Guruswami and Euiwoong Lee , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) , series =. 2017 , publisher =

    work page 2017

  8. [8]

    Mathematics of Operations Research , volume =

    Monique Laurent , title =. Mathematics of Operations Research , volume =

    work page

  9. [9]

    The K -moment problem for compact semi-algebraic sets , journal =

    Konrad Schm. The K -moment problem for compact semi-algebraic sets , journal =

    work page

  10. [10]

    Indiana University Mathematics Journal , volume =

    Mihai Putinar , title =. Indiana University Mathematics Journal , volume =

    work page

  11. [11]

    Annals of Pure and Applied Logic , volume =

    Dima Grigoriev and Nicolai Vorobjov , title =. Annals of Pure and Applied Logic , volume =

    work page

  12. [12]

    Lasserre , title =

    Jean B. Lasserre , title =. SIAM Journal on Optimization , volume =

    work page

  13. [13]

    Hirsch and Dmitrii V

    Dima Grigoriev and Edward A. Hirsch and Dmitrii V. Pasechnik , title =. Proceedings of the 19th International Symposium on Theoretical Aspects of Computer Science (STACS 2002) , pages =

    work page 2002

  14. [14]

    Journal of Pure and Applied Algebra , volume =

    Mareike Dressler , title =. Journal of Pure and Applied Algebra , volume =

    work page

  15. [15]

    2003 , note =

    Grigoriy Blekherman , title =. 2003 , note =

    work page 2003

  16. [16]

    Sum-of-squares hierarchy lower bounds for symmetric formulations , booktitle =

    Adam Kurpisz and Samuli Lepp. Sum-of-squares hierarchy lower bounds for symmetric formulations , booktitle =

    work page

  17. [17]

    Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , series =

    Adam Kurpisz and Aaron Potechin and Elias Samuel Wirth , title =. Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) , series =. 2021 , publisher =

    work page 2021

  18. [18]

    Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , series =

    Adam Kurpisz , title =. Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) , series =. 2019 , publisher =

    work page 2019

  19. [19]

    On the hardest problem formulations for the 0/1 Lasserre hierarchy , journal =

    Adam Kurpisz and Samuli Lepp. On the hardest problem formulations for the 0/1 Lasserre hierarchy , journal =

    work page

  20. [20]

    Computational Complexity , volume =

    Dima Grigoriev , title =. Computational Complexity , volume =

    work page

  21. [21]

    Parrilo , title =

    Pablo A. Parrilo , title =

    work page

  22. [22]

    Goemans and David P

    Michel X. Goemans and David P. Williamson , title =. Journal of the ACM , volume =

    work page

  23. [23]

    On the Shannon capacity of a graph , journal =

    L. On the Shannon capacity of a graph , journal =

    work page

  24. [24]

    Proceedings of the International Congress of Mathematicians (ICM 2014), Volume IV , pages =

    Boaz Barak and David Steurer , title =. Proceedings of the International Congress of Mathematicians (ICM 2014), Volume IV , pages =. 2014 , publisher =

    work page 2014

  25. [25]

    Lasserre , title =

    Jean B. Lasserre , title =

    work page

  26. [26]

    Emerging Applications of Algebraic Geometry , pages =

    Monique Laurent , title =. Emerging Applications of Algebraic Geometry , pages =. 2008 , publisher =

    work page 2008

  27. [27]

    Mathematics of Operations Research , volume =

    William Cook and Sanjeeb Dash , title =. Mathematics of Operations Research , volume =

    work page

  28. [28]

    Coppersmith--Rivlin type inequalities and the order of vanishing of polynomials at 1 , journal =

    Tam. Coppersmith--Rivlin type inequalities and the order of vanishing of polynomials at 1 , journal =

    work page

  29. [29]

    Don Coppersmith and T. J. Rivlin , title =. SIAM Journal on Mathematical Analysis , volume =

    work page

  30. [30]

    Proceedings of the 31st Conference on Computational Complexity (CCC 2016) , pages =

    Troy Lee and Anupam Prakash and Ronald de Wolf and Henry Yuen , title =. Proceedings of the 31st Conference on Computational Complexity (CCC 2016) , pages =. 2016 , publisher =

    work page 2016

  31. [31]

    Parrilo and Rekha R

    Grigoriy Blekherman and Pablo A. Parrilo and Rekha R. Thomas , title =

    work page