{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidlozpk7tfyw5sprjzb4svl6mkrou4ntt5l5qerxyubhpcg6totma",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mjebcpcwv6f2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.08731v1",
  "publishedAt": "2026-04-13T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Noah G. Singer",
    "Madhur Tulsiani",
    "Santhoshini Velusamy"
  ],
  "textContent": "**Authors:** Noah G. Singer, Madhur Tulsiani, Santhoshini Velusamy\n\nFor an arbitrary family of predicates $\\mathcal{F} \\subseteq \\\\{0,1\\\\}^{[q]^k}$ and any $ε> 0$, we prove a single-pass, linear-space streaming lower bound against the gap promise problem of distinguishing instances of Max-CSP$({\\mathcal{F}})$ with at most $β+ε$ fraction of satisfiable constraints from instances of with at least $γ-ε$ fraction of satisfiable constraints, whenever Max-CSP$({\\mathcal{F}})$ admits a $(γ,β)$-integrality gap instance for the basic LP. This subsumes the linear-space lower bound of Chou, Golovnev, Sudan, Velingker, and Velusamy (STOC 2022), which applies only to a special subclass of CSPs with linear-algebraic structure. (Their result itself generalizes work of Kapralov and Krachun (STOC 2019) for Max-CUT.) Our approach identifies the right ``analytic'' analogues of previously-used linear-algebraic conditions; this yields substantial simplifications while capturing a much larger class of problems. Our lower bound is essentially optimal for single-pass streaming, since: (1) All CSPs admit $(1-ε)$-approximations in quasilinear space, and (2) sublinear-space streaming algorithms can simulate the LP (on bounded-degree instances), giving approximation algorithms when integrality gap instances do not exist. The starting point for our lower bound is a reduction from a \"distributional implicit hidden partition'' problem defined by Fei, Minzer, and Wang (STOC 2026) in the context of multi-pass streaming. Our result is an analogue of theirs in the single-pass setting, where we obtain a much stronger (and tight) space lower bound.",
  "title": "Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs"
}