{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiatryzxspqtwut5j2b2y5as3ywwih2r2nihapt75j5ufn7doqs6ty",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mkz5e7yaa4u2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.00594v1",
  "publishedAt": "2026-05-04T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Adam Kurpisz",
    "Lucas Slot",
    "Mikhail Zaytsev"
  ],
  "textContent": "**Authors:** Adam Kurpisz, Lucas Slot, Mikhail Zaytsev\n\nWe 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 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\"\"",
  "title": "On the Distribution of Unweighted Minimum Knapsack Instances with Large SOS Rank"
}