Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs
Abstract
We prove that any linear $3$-query locally correctable code C : 𝔽2k → 𝔽2n with constant correction radius must have length n ≥ 2Ω(√k). This improves on the prior best lower bound of 2Ω(√(k/log k)), due to [AG24], and shows that the folklore construction of linear $3$-LCCs from Reed-Muller codes, which achieve length n = 2O(√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.
Related
- Optimal self-orthogonal binary linear codes
- Explicit construction of optimal binary linear complementary pairs via Belov codes
- Some Results on the Weight Spectrum of Binary Reed-Muller Codes $RM(m-7,m)$
- New binary optimal LCD codes using heuristic embedding
- A machine-checked proof of the Dong-Yang classification of optimal (n,4) binary codes for BSCs
BibTeX
@misc{janzer2026reedmuller,
title = {{Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs}},
author = {Oliver Janzer and Peter Manohar},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03145},
eprint = {2611.03145},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03145},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs
AU - Oliver Janzer
AU - Peter Manohar
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03145
UR - https://arxiv.org/abs/2611.03145
AB - We prove that any linear $3$-query locally correctable code C : 𝔽_2^k → 𝔽_2^n with constant correction radius must have length n ≥ 2^Ω(√k). This improves on the prior best lower bound of 2^Ω(√(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(√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.
ER -