Relaxed Locally Correctable Codes

Wednesday, March 21, 2018 - 4:30pm to Thursday, March 22, 2018 - 4:55pm

Event Calendar Category

LIDS & Stats Tea

Speaker Name

Govind Ramnarayan



Building and Room Number

LIDS Lounge


Locally decodable codes (resp. locally correctable codes), or LDCs (resp. LCCs), are codes for which individual symbols of the message (resp. codeword) and be recovered by reading just a few bits from a noisy codeword, which is corrupted with adversarial noise. Such codes have been very useful in theory and practice, but suffer from a poor tradeoff between the rate of the code and the query complexity of its local decoder (resp. corrector).

A natural relaxation of locally decodable codes (LDCs) considered by Ben-Sasson et al. (SICOMP, 2006) allows the decoder to "reject" when it sees too many errors to decode the desired bit of the message. They show that, when the decoder is given this liberty, there exist codes with a rate that is subexponentially better than that of the best constant-query locally decodable codes known today.

We extend their relaxation to locally correctable codes and achieve similar savings in complexity compared to existing LCCs. Specifically, our codes have:

1. Subexponentially lower rate than existing LCCs in the constant-query regime.

2. Nearly subexponentially lower query complexity than existing LCCs in the constant-rate regime.

Ramnarayan will outline the first result and some of the techniques used in the construction. Time permitting, I'll say a few words about how the second result is proved. Joint work with Tom Gur and Ron Rothblum.


Govind Ramnarayan is a 4th year Ph.D. student in CSAIL, formerly advised by Dana Moshkovitz and currently advised by Elchanan Mossel. He is widely interested in theoretical computer science and related areas, with a specific interest in hardness of approximation, coding theory, and boolean analysis.