← 研踪 PaperTrailarXiv:2610.38664 · v1
Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
首次提交 2026-10-29 02:49
版本更新 2026-10-29 02:49
雷达观测 2026-10-30 10:22
摘要
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$.
作者备注：24 pages
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-10-29 02:49 · 最新观测版本
Upper Bounds for CSP Non-redundancy via Locally Decodable Codes
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$.
查看此版本解读 →查看此版本原文 ↗