{"id":"arxiv/2610.38664","url":"https://arxiv.org/abs/2610.38664","tags":["cs.DM","cs.CC","cs.IT","math.CO"],"score":0,"title":"Upper Bounds for CSP Non-redundancy via Locally Decodable Codes","domain":"cs.DM","source":"arxiv","authors":["Joshua Brakensiek","David Conlon","Venkatesan Guruswami","Xiaoyu He","Jiaxi Nie","Maya Sankar","Hung-Hsun Hans Yu"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-28","reactions":{}}