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