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

Abstract

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. The crux of our argument is to show that a certain edge-coloured Kikuchi graph has a unique colour cycle: a cycle in which some colour is used exactly once. We do this by controlling the distribution of colours at each vertex in the graph using a random walk mixing argument and a novel hypergraph decomposition based on edge expansion of the hypergraph's "flattening" into a graph.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Information Theory

• arXiv preprint · 2 November 2026

  Large independent sets via neighborhood block dynamics, Glauber dynamics, and local occupancy

  Ewan Davies and Brian Tan
• arXiv preprint · 3 November 2026

  Testing Implies Distance Estimation with Polynomial Loss

  Gaia Carenini and Cameron Seth
• arXiv preprint · 2 November 2026

  Full-Rank Constructions of Explicit Lossless Expanders and Good Small-Set qLTCs

  Yali Aharon-Holzman, Michael Ilan, Assaf Reiner and 1 other
• arXiv preprint · 3 November 2026

  Glauber Dynamics for Sampling Colorings: Rapid Mixing above $(1+1/\mathrm{e})Δ$ via Hidden Hard-Core Models

  Xiongxin Yang
• arXiv preprint · 3 November 2026

  A Short Proof and Generalization of the Rainbow Cycle Theorem and Improved Bounds for Binary Even-Query LCCs

  Andrew D. Lin

All new papers in Information Theory