Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
Abstract
In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form nk± o(1) for some positive integer k.
Related
- Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator
- Amortized Relaxed Locally Decodable Codes
- Lower Bounds for all List-Decodable Deletion Codes
- Data Protection in Function-Correcting Symbol-Pair Codes: Redundancy Bounds and Protection Profiles
- Alphabet-Dependent Bounds for Pure Quantum (r,ρ)-Locally Recoverable Codes
BibTeX
@misc{brakensiek2026upper,
title = {{Upper Bounds for CSP Non-redundancy via Locally Decodable Codes}},
author = {Joshua Brakensiek and David Conlon and Venkatesan Guruswami and Xiaoyu He and Jiaxi Nie and Maya Sankar and Hung-Hsun Hans Yu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38664},
eprint = {2610.38664},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38664},
}
RIS
TY - UNPB
TI - Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
AU - Joshua Brakensiek
AU - David Conlon
AU - Venkatesan Guruswami
AU - Xiaoyu He
AU - Jiaxi Nie
AU - Maya Sankar
AU - Hung-Hsun Hans Yu
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38664
UR - https://arxiv.org/abs/2610.38664
AB - In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form n^k± o(1) for some positive integer k.
ER -