{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiggwotpkzd72ozqm3swcpgflp2wxlgpl7upryvhnwvawcr6l6y5re",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mluiyi55dqf2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.14007v1",
  "publishedAt": "2026-05-15T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Amatya Sharma",
    "Santhoshini Velusamy"
  ],
  "textContent": "**Authors:** Amatya Sharma, Santhoshini Velusamy\n\nNon-redundancy, introduced by Bessiere, Carbonnel, and Katsirelos (AAAI 2020), is a structural parameter for Constraint Satisfaction Problems ($\\mathsf{CSPs}$) that governs kernelization, exact and approximate sparsification, and exact streaming complexity. It is the largest size of a $\\mathsf{CSP}$ instance admitting no smaller subinstance with the same satisfying assignments. We study non-redundancy $\\mathsf{NRD}_n(R)$ for Boolean symmetric $\\mathsf{CSPs}$ defined by an $r$-ary relation $R$ whose value depends only on Hamming weight. An instance of $\\mathsf{CSP}(R)$ has $n$ variables and constraints given by $r$-tuples; a constraint is satisfied exactly when the induced tuple lies in $R$. This class includes natural predicates such as cuts and $k$-SAT clauses. Our main result is a near-complete classification of the asymptotic growth of $\\mathsf{NRD}_n(R)$ for symmetric Boolean predicates of arity at most $5$. Using computational experiments and algebraic upper- and lower-bound criteria, we resolve every predicate of arity at most $4$ and all but two predicates of arity $5$. For upper bounds, we introduce $t$-balancedness, a lifted, higher-degree version of the balancedness notion of Chen, Jansen, and Pieterse (Algorithmica 2020). We prove that $t$-balancedness is equivalent to the existence of degree-$t$ multilinear polynomials capturing $R$, and hence implies $\\mathsf{NRD}_n(R)=O(n^t)$. For lower bounds, we use Carbonnel's (CP 2022) framework: predicates admitting a special reduction from $k$-ary OR inherit OR's lower bound $Ω(n^k)$. The only unresolved arity-$5$ predicates in our framework have bounds $Ω(n^2)$ and $O(n^3)$; we reduce their exact classification to natural extremal set-system questions.",
  "title": "Non-Redundancy of Low-Arity Symmetric Boolean CSPs"
}