Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

A stronger bound for linear 3-LCC
event speaker icon
Tal Yankovitz (Tel Aviv University)
event date icon
Wednesday, 21.08.2024, 13:00
event location icon
Amado 814

A q-locally correctable code (LCC) C:{0,1}^k->{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^Ω(k^1/8) . In this work we prove that n=2^Ω(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^Ω(k^1/3).