Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances

Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen, Victor Lagerkvist, Magnus Wahlström

arXivarxiv/2605.19055May 18, 2026cs.DMscore 0

We say that an instance of a constraint satisfaction problem (CSP) is non-redundant if the satisfaction of each clause cannot be implied by the satisfaction of the other clauses in the instance. The non-redundancy (NRD) of a CSP is the maximal number of clauses a non-redundant instance can have for a given number of variables. NRD is closely tied to the behavior of CSPs in various computational models including their sparsification, kernelization, and streaming complexity. A primary open question in the study of non-redundancy is the identification of which CSP predicates have near-linear…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.19055
curl -X POST /api/v1/records/arxiv/2605.19055/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.19055/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'