Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
Abstract
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 NRD. Recent works by Carbonnel [CP 2022], Khanna, Putterman and Sudan [STOC 2025], Brakensiek and Guruswami [STOC 2025] and Brakensiek, Guruswami, Jansen, Lagerkvist, and Wahlström [2025] have introduced various forms of gadget reductions between CSPs to relate their non-redundancy. The primary contribution of this work is to recontextualize many of these gadget reductions in a framework which we call hypergraph projections. By studying a quantity we call the shrinking factor of these hypergraph projections, we can more precisely predict when a gadget reduction between predicates can yield a super-linear NRD lower bound, greatly improving on the analysis of previous works. To illustrate the power of our framework, we identify some concrete CSP predicates whose non-redundancy is at the cusp of our understanding and show how our methods give lower bounds that could not have been achieved with previous methods. We also demonstrate how these gadget reductions can be automatically deduced using SAT solvers, thereby opening up novel computational avenues for discovering further relationships between the non-redundancy of various CSPs.
Related
- Improved upper bounds for five IHTC-2024 benchmark instances via exact reoptimization of the nurse-to-room layer
- Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
- Data Protection in Function-Correcting Symbol-Pair Codes: Redundancy Bounds and Protection Profiles
- The Gaudin model and the super Bethe ansatz for unitarizable modules over the general linear Lie (super)algebra
- Super-approximation and optimal L2 convergence of the stabilized BGN method with piecewise linear parametric finite elements for curve-shortening flow
BibTeX
@misc{brakensiek2026superlinear,
title = {{Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances}},
author = {Joshua Brakensiek and Venkatesan Guruswami and Bart M. P. Jansen and Victor Lagerkvist and Magnus Wahlström},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.19055},
eprint = {2605.19055},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.19055},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances
AU - Joshua Brakensiek
AU - Venkatesan Guruswami
AU - Bart M. P. Jansen
AU - Victor Lagerkvist
AU - Magnus Wahlström
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2605.19055
UR - https://arxiv.org/abs/2605.19055
AB - 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 NRD. Recent works by Carbonnel [CP 2022], Khanna, Putterman and Sudan [STOC 2025], Brakensiek and Guruswami [STOC 2025] and Brakensiek, Guruswami, Jansen, Lagerkvist, and Wahlström [2025] have introduced various forms of gadget reductions between CSPs to relate their non-redundancy. The primary contribution of this work is to recontextualize many of these gadget reductions in a framework which we call hypergraph projections. By studying a quantity we call the shrinking factor of these hypergraph projections, we can more precisely predict when a gadget reduction between predicates can yield a super-linear NRD lower bound, greatly improving on the analysis of previous works. To illustrate the power of our framework, we identify some concrete CSP predicates whose non-redundancy is at the cusp of our understanding and show how our methods give lower bounds that could not have been achieved with previous methods. We also demonstrate how these gadget reductions can be automatically deduced using SAT solvers, thereby opening up novel computational avenues for discovering further relationships between the non-redundancy of various CSPs.
ER -