Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > OLIVER JANZER:
All reports by Author Oliver Janzer:

TR26-291 | 2nd November 2026
Oliver Janzer, Peter Manohar

Reed–Muller Codes are Optimal Binary Linear 3-Query LCCs

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, ... more >>>




ISSN 1433-8092 | Imprint