A stronger bound for linear 3-LCC

Add to your list(s) Download to your calendar using vCal

• Tal Yankovitz (Tel-Aviv University)
• Tuesday 28 January 2025, 14:00-15:00
• Computer Laboratory, William Gates Building, Room SS03.

If you have a question about this talk, please contact Tom Gur.

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^Ω(k1/8) . In this work we prove that n=2^Ω(k1/4) . As Reed-Muller codes yield 3-LCC with n=2^O(k1/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^Ω(k1/3).

This talk is part of the Algorithms and Complexity Seminar series.

This talk is included in these lists:

• Algorithms and Complexity Seminar
• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, William Gates Building, Room SS03
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ki287

Note that ex-directory lists are not shown.