Reed-Muller codes are optimal for linear 3-query locally correctable codes (LCCs) with constant correction radius.

TR26-291 | Reed–Muller Codes are Optimal Binary Linear 3-Query LCCs | Oliver Janzer, Peter Manohar https://eccc.weizmann.ac.il/report/2026/291 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^{Omega(sqrt{k})}$. This improves on the prior best lower bound of $2^{Omega(sqrt{k/log k})}$, due to [AG24], and shows that the folklore construction of linear $3$-LCCs from

Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs https://arxiv.org/abs/2611.03145v1 Authors: Oliver Janzer, Peter ManoharWe 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 achie