Binary Error Correcting Codes with Minimal Noiseless Feedback
0Rachel Zhang (Massachusetts Institute of Technology)
https://simons.berkeley.edu/talks/rachel-zhang-massachusetts-institute-technology-2024-04-08
Advances in the Theory of Error-Correcting Codes
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.