Constraint problem complexity limited with code theory insights
Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
Discrete MathematicsComputational ComplexityInformation Theory
Summary
Constraint satisfaction problems (CSPs) involve many conditions that must all be true, but some conditions can be redundant. The authors studied how to find upper limits on the number of truly independent conditions in these problems. They connected this question to a special kind of error-correcting codes called locally decodable and correctable codes, which have limitations on their structure. Using these connections, the authors improved previous limits on CSP redundancy and found a special example that breaks common patterns.
What this means in practice
- •For optimization engineers: Design tighter constraints in CSP models to reduce unnecessary conditions and improve solver efficiency for complex decision problems.
- •For data streaming designers: Apply improved redundancy bounds to develop more efficient streaming algorithms that handle constraints with fewer resources.
A theory result. No direct application yet.
Authors
Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie, Maya Sankar, Hung-Hsun Hans Yu
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 $n^{k\pm o(1)}$ for some positive integer $k$.