{"id":"arxiv/2611.03145","url":"https://arxiv.org/abs/2611.03145","tags":["cs.IT","cs.CC","math.CO"],"score":0,"title":"Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs","domain":"cs.IT","source":"arxiv","authors":["Oliver Janzer","Peter Manohar"],"reviews":0,"subject":"cs.IT","summary":"We prove that any linear $3$-query locally correctable code $C \\colon \\mathbb{F}_2^k \\to \\mathbb{F}_2^n$ with constant correction radius must have length $n \\geq 2^{Ω(\\sqrt{k})}$. This improves on the prior best lower bound of $2^{Ω(\\sqrt{k/\\log k})}$, due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed-Muller codes, which achieve length $n = 2^{O(\\sqrt{k})}$, is optimal up to constant factors in the exponent. Our proof builds on the approach of [KM24a], further refined in [Yan24,KM24b], that uses \"chain derived equations\" in combination with Kikuchi graphs.…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}