Reed-Muller codes are best binary linear codes correcting with three queries
Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs
Information TheoryComputational Complexity
Summary
The paper shows that any binary linear code that can fix errors by looking at only three parts of the code must be at least as long as a specific size, improving on previous lower bounds. This means the well-known Reed-Muller codes, which have this property, are essentially the shortest possible codes with such local correction ability. The authors use sophisticated math tools like special graphs and random walks to prove this unique and optimal length property.
What this means in practice
- •For coding theory engineers: Confirm that no shorter linear 3-query error-correcting codes exist, guiding design limits of efficient error correction schemes.
- •For cryptographic protocol designers: Use the optimal length bound of 3-query locally correctable codes to set realistic parameters in secure multi-party computation and privacy protocols.
A theory result. No direct application yet.
Authors
Oliver Janzer, Peter Manohar
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.