Metraipolis › archive › dc_97a768f37cc3
Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs — arXiv:2611.03145
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03145
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:51:35.801Z
- SHA-256 of the archived text
3a6d572a77d63eecca79d86cc8dabafc75b5fc100c9f38c9d748b86b72f210b5- Stable URL of this page
https://metraipolis.com/documento/dc_97a768f37cc3
How to cite
Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs — arXiv:2611.03145 — arXiv (en), https://arxiv.org/abs/2611.03145 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_97a768f37cc3 (Metraipolis archive dc_97a768f37cc3, sha256 3a6d572a77d63eecca79d86cc8dabafc75b5fc100c9f38c9d748b86b72f210b5)
BibTeX
@misc{dc97a768f37cc3,
title = {Reed-Muller Codes are Optimal Binary Linear 3-Query LCCs — arXiv:2611.03145},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03145},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_97a768f37cc3; sha256 3a6d572a77d63eecca79d86cc8dabafc75b5fc100c9f38c9d748b86b72f210b5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03145. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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, 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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Information Theory (cs.IT) ; Computational Complexity (cs.CC); Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.03145 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T18:15:38.141Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).