{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib7mebqcldbuhbfktiic6a5mh3swaw5bed57cm4smzddjcmcq2iwe",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mk7svtf3pfq2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.21922v1",
  "publishedAt": "2026-04-24T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Amatya Sharma",
    "Santhoshini Velusamy"
  ],
  "textContent": "**Authors:** Amatya Sharma, Santhoshini Velusamy\n\nWe study the single-pass streaming complexity of deciding satisfiability of Constraint Satisfaction Problems (CSPs). A CSP is specified by a constraint language $Γ$, that is, a finite set of $k$-ary relations over the domain $[q] = \\\\{0, \\dots, q-1\\\\}$. An instance of $\\mathsf{CSP}(Γ)$ consists of $m$ constraints over $n$ variables $x_1, \\ldots, x_n$ taking values in $[q]$. Each constraint $C_i$ is of the form $\\\\{R_i,(x_{i_1} + λ_{i_1}, \\ldots, x_{i_k} + λ_{i_k})\\\\}$, where $R_i \\in Γ$ and $λ_{i_1}, \\ldots, λ_{i_k} \\in [q]$ are constants; it is satisfied if and only if $(x_{i_1} + λ_{i_1}, \\ldots, x_{i_k} + λ_{i_k}) \\in R_i$, where addition is modulo $q$. In the streaming model, constraints arrive one by one, and the goal is to determine, using minimum memory, whether there exists an assignment satisfying all constraints. For $k$-SAT, Vu (TCS 2024) proves an optimal $Ω(n^k)$ space lower bound, while for general CSPs, Chou, Golovnev, Sudan, and Velusamy (JACM 2024) establish an $Ω(n)$ lower bound; a complete characterization has remained open. We close this gap by showing that the single-pass streaming space complexity of $\\mathsf{CSP}(Γ)$ is precisely governed by its non-redundancy, a structural parameter introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020). The non-redundancy $\\mathsf{NRD}_n(Γ)$ is the maximum number of constraints over $n$ variables such that every constraint $C$ is non-redundant, i.e., there exists an assignment satisfying all constraints except $C$. We prove that the single-pass streaming complexity of $\\mathsf{CSP}(Γ)$ is characterized, up to a logarithmic factor, by $\\mathsf{NRD}_n(Γ)$.",
  "title": "Characterizing Streaming Decidability of CSPs via Non-Redundancy"
}