ECCC-Report TR24-036https://eccc.weizmann.ac.il/report/2024/036Comments and Revisions published for TR24-036en-usSat, 06 Apr 2024 20:00:22 +0300
Revision 2
| A stronger bound for linear 3-LCC |
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2024/036#revision2A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the cases that $C$ is linear.
In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC $n = 2^{\Omega(k^{1/8})}$. In this work we prove that $n = 2^{\Omega(k^{1/4})}$. As Reed-Muller codes yield 3-LCC with $n = 2^{O(k^{1/2})}$, this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is $n = 2^{\Omega(k^{1/3})}$.Sat, 06 Apr 2024 20:00:22 +0300https://eccc.weizmann.ac.il/report/2024/036#revision2
Revision 1
| A stronger bound for linear 3-LCC |
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2024/036#revision1A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the cases that $C$ is linear.
In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC $n = 2^{\Omega(k^{1/8})}$. In this work we prove that $n = 2^{\Omega(k^{1/4})}$. As Reed-Muller codes yield 3-LCC with $n = 2^{O(k^{1/2})}$, this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is $n = 2^{\Omega(k^{1/3})}$.Mon, 26 Feb 2024 11:44:09 +0200https://eccc.weizmann.ac.il/report/2024/036#revision1
Paper TR24-036
| A stronger bound for linear 3-LCC |
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2024/036A $q$-locally correctable code (LCC) $C:\{0,1\}^k \to \{0,1\}^n$ is a code in which it is possible to correct every bit of a (not too) corrupted codeword by making at most $q$ queries to the word. The cases in which $q$ is constant are of special interest, and so are the cases that $C$ is linear.
In a breakthrough result Kothari and Manohar (STOC 2024) showed that for linear 3-LCC $n = 2^{\Omega(k^{1/8})}$. In this work we prove that $n = 2^{\Omega(k^{1/4})}$. As Reed-Muller codes yield 3-LCC with $n = 2^{O(k^{1/2})}$, this brings us closer to closing the gap. Moreover, in the special case of design-LCC (into which Reed-Muller fall) the bound we get is $n = 2^{\Omega(k^{1/3})}$.Sun, 25 Feb 2024 07:29:45 +0200https://eccc.weizmann.ac.il/report/2024/036