אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

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).