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 #2 to TR24-036 | 6th April 2024 20:00

A stronger bound for linear 3-LCC

RSS-Feed




Revision #2
Authors: Tal Yankovitz
Accepted on: 6th April 2024 20:00
Downloads: 24
Keywords: 


Abstract:

A $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})}$.



Changes to previous version:

- Added analysis for the case of larger alphabets
- Added a proof sketch for Fact 2.3
- Minor changes


Revision #1 to TR24-036 | 26th February 2024 11:44

A stronger bound for linear 3-LCC





Revision #1
Authors: Tal Yankovitz
Accepted on: 26th February 2024 11:44
Downloads: 99
Keywords: 


Abstract:

A $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})}$.


Paper:

TR24-036 | 21st February 2024 10:50

A stronger bound for linear 3-LCC





TR24-036
Authors: Tal Yankovitz
Publication: 25th February 2024 07:29
Downloads: 151
Keywords: 


Abstract:

A $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})}$.



ISSN 1433-8092 | Imprint