Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-296-FOCS24-315
DOI: 10.1137/24m1718524 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 15.04.2026. Verfasst von Omar Alrabiah und 1 weiteren Autor:innen. Die Arbeit nennt 51 Literaturangaben. Gefördert von: Saudi Arabian Cultural Mission, National Science Foundation, Simons Foundation.
Abstract (Originalsprache)
We prove that a binary linear code of blocklength [Formula: see text] that is locally correctable with 3 queries against a fraction [Formula: see text] of adversarial errors must have dimension at most [Formula: see text]. This is almost tight in view of quadratic Reed–Muller codes being a 3-query locally correctable code (LCC) with dimension [Formula: see text]. Our result improves, for the binary field case, the [Formula: see text] bound obtained in the recent breakthrough of [P. K. Kothari and P. Manohar, in Proceedings of the 56 th Annual ACM Symposium on Theory of Computing, ACM, New York, 2024, pp. 776–787] and the more recent improvement to [Formula: see text] of [T. Yankovitz, in Proceedings of the 2024 IEEE 65 th Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2024, pp. 1786–1801]. Previous bounds for 3-query linear LCCs proceed by constructing a 2-query locally decodable code (LDC) from the 3-query linear LCC/LDC and applying the strong bounds known for the former. Our approach is more direct and proceeds by bounding the covering radius of the dual code, borrowing inspiration from [E. Iceland and A. Samorodnitsky, Discrete Comput. Geom., 63 (2020), pp. 560–576]. That is, we show that if [Formula: see text] is an arbitrary encoding map [Formula: see text] for the 3-query LCC, then all vectors in [Formula: see text] can be written as a [Formula: see text]-sparse linear combination of the [Formula: see text]’s, which immediately implies [Formula: see text]. The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least [Formula: see text] of the [Formula: see text]’s. We achieve this using the recent breakthrough result of [N. Alon et al., Proc. Lond. Math. Soc. (3), 130 (2025), e70044] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.
Förderung
- Saudi Arabian Cultural Mission
- National Science Foundation
- Simons Foundation
Zitieren
APA
Alrabiah, O., & Guruswami, V. (2026). Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. SIAM Journal on Computing, 55(5), FOCS24-296-FOCS24-315. https://doi.org/10.1137/24m1718524
Vancouver
Alrabiah O, Guruswami V. Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles. SIAM Journal on Computing. 2026;55(5):FOCS24-296-FOCS24-315. doi:10.1137/24m1718524
BibTeX
@article{Alrabiah2026,
author = {Alrabiah, Omar and Guruswami, Venkatesan},
title = {Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {5},
pages = {FOCS24--296--FOCS24--315},
doi = {10.1137/24m1718524}
}
EUVIMED