{"id":"arxiv/2605.19055","url":"https://arxiv.org/abs/2605.19055","tags":["cs.DM","cs.LO","math.CO"],"score":0,"title":"Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances","domain":"cs.DM","source":"arxiv","authors":["Joshua Brakensiek","Venkatesan Guruswami","Bart M. P. Jansen","Victor Lagerkvist","Magnus Wahlström"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-18","reactions":{}}