Binary Error-Correcting Codes with Minimal Noiseless Feedback

In the setting of error-correcting codes with feedback, Alice wishes to communicate a k-bit message x to Bob by sending a sequence of bits over a channel while noiselessly receiving feedback from Bob. It has been long known (Berlekamp, 1964) that in this model, Bob can still correctly determine x even if ≈ frac13 of Alice's bits are flipped adversarially. This improves upon the classical setting without feedback, where recovery is not possible for error fractions exceeding frac14. The original feedback setting assumes that after transmitting each bit, Alice knows (via feedback) what bit Bob received. In this work, our focus in on the limited feedback model, where Bob is only allowed to send a few bits at a small number of pre-designated points in the protocol. For any desired ε > 0, we construct a coding scheme that tolerates a fraction 1/3-ε of bit flips relying only on Oε(log k) bits of feedback from Bob sent in a fixed Oε(1) number of rounds. We complement this with a matching lower bound showing that Omega(log k) bits of feedback are necessary to recover from an error fraction exceeding 1/4 (the threshold without any feedback), and for schemes resilient to a fraction 1/3-ε of bit flips, the number of rounds must grow as ε → 0. We also study (and resolve) the question for the simpler model of erasures. We show that Oε(log k) bits of feedback spread over Oε(1) rounds suffice to tolerate a fraction (1-ε) of erasures. Likewise, our Omega(log k) lower bound applies for erasure fractions exceeding 1/2, and an increasing number of rounds are required as the erasure fraction approaches 1.