{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigstaqugmwpzdl75r47aw4khe4maatkjpph7yunybhz5av7nje4xm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mj3kzssmsjc2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.07278v1",
  "publishedAt": "2026-04-09T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Matvey Mosievskiy",
    "Lev Reyzin"
  ],
  "textContent": "**Authors:** Matvey Mosievskiy, Lev Reyzin\n\nWe study computational limitations in \\emph{multi-plant} average-case inference problems, in which $t$ disjoint planted structures of size $k$ are embedded in a random background on $n$ elements. A natural parameter in this setting is the total planted size $K := kt$. For several classic planted-subgraph problems, including planted clique, existing algorithmic and lower-bound evidence suggests a characteristic computational threshold near $\\sqrt{n}$ in the single-plant setting. Our main result is a Sum-of-Squares (SoS) integrality gap for refuting the presence of multiple planted cliques. Specifically, for $G \\sim G(n,1/2)$, we construct a degree-$d$ SoS pseudoexpectation for the natural relaxation that maximizes the total size of up to $t$ disjoint cliques. Throughout the regime $kt \\le n^{1/2 - c\\sqrt{d/\\log n}},$ for a universal constant $c>0$, this relaxation achieves objective value $kt(1-o(1))$, and therefore degree-$d$ SoS cannot certify an upper bound below $kt$. This extends the planted-clique SoS lower bounds of~\\cite{BarakHKKMP19} to a multi-plant setting with explicit disjointness constraints. As complementary evidence from a different computational model, we prove a lower bound in the statistical query (SQ) framework, extending the results of~\\cite{FeldmanGRVX17}. We show that for detecting $t$ disjoint planted $k \\times k$ bicliques (equivalently, a row-mixture distribution), when $kt = O(n^{1/2-δ})$ for any fixed $δ>0$, no polynomial-time SQ algorithm can distinguish the planted and null distributions with constant advantage.",
  "title": "Multiple Planted Structures Below $\\sqrt{n}$: An SoS Integrality Gap and an SQ Lower Bound"
}