Binary Error Correcting Codes with Minimal Noiseless Feedback

Speaker: Rachel Zhang , CSAIL MIT

Date: Friday, September 15, 2023

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: G-882 Hewlett Room

Event Type: Seminar

Room Description:

Host: Vinod Vaikuntanathan , CSAIL / EECS

Contact: Felicia Raton, fraton@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: Binary Error Correcting Codes with Minimal Noiseless Feedback

In an error correcting code with feedback, Alice wishes to communicate a k-bit message to Bob by sending a sequence of bits over a channel while receiving noiseless feedback about what has been received. It has long been known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if 1/3 of Alice's bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding 1/4.

The original feedback setting assumes that Alice receives feedback each time she transmits a bit. In this talk, we will discuss the limited feedback model, where Bob is only allowed to send a few bits of feedback at a small number of pre-designated points in the protocol. We will give optimal constructions of feedback codes for both the error and erasure settings and prove matching lower bounds.

Joint work with Meghal Gupta and Venkatesan Guruswami. https://arxiv.org/pdf/2212.05673.pdf

Research Areas:

Impact Areas:

See other events that are part of the CSAIL Security Seminar Series 2023 - 2024.

Created by Megan F Farmer Email at Friday, September 08, 2023 at 5:07 PM.