Tata Institute of Fundamental Research
Binary Interactive Codes with Erasure Resilience > 1/2
STCS Student Seminar
Speaker:
Bikshan Chatterjee (TIFR)
Organiser:
Santanu Das
Date:
Friday, 21 Mar 2025, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
Coding for Interactive Communication" is the study of making interactive protocols resilient to errors. But we can ask the following question: what if the original protocol was only sending a single message from Alice to Bob ? Can using interaction (allowing Bob to send noisy feedback) help them achieve higher error-resilience than what is possible with error correcting codes ?
We will see a binary interactive protocol achieving erasure resilience 6/11 (greater than 1/2 which is the plotkin bound barrier for erasure resilience using normal error correcting codes).
The talk will be based on the paper "Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to > 1/2 Adversarial Corruption" by Meghal Gupta, Yael Tauman Kalai and Rachel Yun Zhang.
Reference: https://arxiv.org/abs/2111.04181.
| Speaker: | Bikshan Chatterjee (TIFR) |
| Organiser: | Santanu Das |
| Date: | Friday, 21 Mar 2025, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
Coding for Interactive Communication" is the study of making interactive protocols resilient to errors. But we can ask the following question: what if the original protocol was only sending a single message from Alice to Bob ? Can using interaction (allowing Bob to send noisy feedback) help them achieve higher error-resilience than what is possible with error correcting codes ?
We will see a binary interactive protocol achieving erasure resilience 6/11 (greater than 1/2 which is the plotkin bound barrier for erasure resilience using normal error correcting codes).
The talk will be based on the paper "Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to > 1/2 Adversarial Corruption" by Meghal Gupta, Yael Tauman Kalai and Rachel Yun Zhang.
Reference: https://arxiv.org/abs/2111.04181.