Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-062 | 8th April 2024 09:28

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles

RSS-Feed




Revision #1
Authors: Omar Alrabiah, Venkatesan Guruswami
Accepted on: 8th April 2024 09:28
Downloads: 110
Keywords: 


Abstract:

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a $3$-query locally correctable code (LCC) with dimension $\Theta(\log^2 n)$. Our result improves, for the binary field case, the $O_{\delta}(\log^8 n)$ bound obtained in the recent breakthrough of [Kothari and Manohar, 2023] (and the more recent improvement to $O_{\delta}(\log^4 n)$ for binary linear codes announced in [Yankovitz, 2024]).

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 [Iceland and Samorodnitsky, 2020]. That is, we show that if $x \mapsto (v_1 \cdot x, v_2 \cdot x, \ldots, v_n \cdot x)$ is an arbitrary encoding map $\mathbb{F}_2^k \to \mathbb{F}_2^n$ for the $3$-query LCC, then all vectors in $\mathbb{F}_2^k$ can be written as a $\widetilde{O}_{\delta}(\log n)$-sparse linear combination of the $v_i$'s, which immediately implies $k \le \widetilde{O}_{\delta}((\log n)^2)$. The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least $\widetilde{\Omega}_{\delta}(\log n)$ of the $v_i$'s. We achieve this using the recent breakthrough result of [Alon, Bucic, Sauermann, Zakharov, and Zamir, 2023] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.



Changes to previous version:

Added Theorem 1.3 on improved lower bounds for binary linear $r$-LCCs for odd $r \ge 5$ and accordingly changed Section 4. Removed conjecture relating rainbow and odd even covers.


Paper:

TR24-062 | 5th April 2024 23:16

Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles





TR24-062
Authors: Omar Alrabiah, Venkatesan Guruswami
Publication: 5th April 2024 23:40
Downloads: 136
Keywords: 


Abstract:

We prove that a binary linear code of block length $n$ that is locally correctable with $3$ queries against a fraction $\delta > 0$ of adversarial errors must have dimension at most $O_{\delta}(\log^2 n \cdot \log \log n)$. This is almost tight in view of quadratic Reed-Muller codes being a $3$-query locally correctable code (LCC) with dimension $\Theta(\log^2 n)$. Our result improves, for the binary field case, the $O_{\delta}(\log^8 n)$ bound obtained in the recent breakthrough of [Kothari and Manohar, 2023] (and the more recent improvement to $O_{\delta}(\log^4 n)$ for binary linear codes announced in [Yankovitz, 2024]).

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 [Iceland and Samorodnitsky, 2020]. That is, we show that if $x \mapsto (v_1 \cdot x, v_2 \cdot x, \ldots, v_n \cdot x)$ is an arbitrary encoding map $\mathbb{F}_2^k \to \mathbb{F}_2^n$ for the $3$-query LCC, then all vectors in $\mathbb{F}_2^k$ can be written as a $\widetilde{O}_{\delta}(\log n)$-sparse linear combination of the $v_i$'s, which immediately implies $k \le \widetilde{O}_{\delta}((\log n)^2)$. The proof of this fact proceeds by iteratively reducing the size of any arbitrary linear combination of at least $\widetilde{\Omega}_{\delta}(\log n)$ of the $v_i$'s. We achieve this using the recent breakthrough result of [Alon, Bucic, Sauermann, Zakharov, and Zamir, 2023] on the existence of rainbow cycles in properly edge-colored graphs, applied to graphs capturing the linear dependencies underlying the local correction property.



ISSN 1433-8092 | Imprint