- Relaxed Locally Correctable...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2017
Relaxed Locally Correctable Codes
Speaker:
Govind Ramnarayan
, CSAIL MIT
Date: Wednesday, May 10, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Public: Yes
Location: 32-D463
Event Type:
Room Description:
Host: Pritish Kamath and Akshay Degwekar, CSAIL MIT
Contact: Rebecca Yadegar, ryadegar@csail.mit.edu
Speaker URL: None
Speaker Photo:
None
Reminders to:
seminars@csail.mit.edu, theory-seminars@csail.mit.edu
Reminder Subject:
TALK: Govind Ramnarayan:Relaxed Locally Correctable Codes
Abstract: Locally decodable codes (resp. locally correctable codes), or LDCs (resp. LCCs), are codes for which individual symbols of the message (resp. codeword) can be recovered by reading just a few bits from a noisy codeword. 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 symbol of the message. They show that, when the decoder is given this liberty, there exist codes with 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.
Joint work with Tom Gur and Ron Rothblum.
Research Areas:
Impact Areas:
Created by Rebecca Yadegar at Wednesday, May 03, 2017 at 1:11 PM.