Binary Error-Correcting Codes with Minimal Noiseless Feedback

i 1. How many bits of feedback must Bob send? 2. How many times throughout the protocol must Bob send feedback?

How many bits of feedback? This first question was studied by [HKV15] in the case of errors. In their work, they considered limiting Bob's feedback to δ fraction of Alice's bits. They showed that for randomized protocols, Bob sending any δ > 0 fraction as many bits as Alice is sufficient to achieve the threshold 1 3 error resilience. For deterministic protocols, they showed that if δ > 2 3 is a sufficiently large fraction, 1 3 is achievable, and as δ → 0, the best error resilience they achieve is 1 4 . In this work, we consider an even more limited form of feedback: we allow Bob to send only d total bits rather than δ fraction of Alice's bits, where d does not scale proportionally to the number of bits Alice sends (which necessarily must be more than k bits) or even to k. In particular, we ask if we can achieve error resilience 1 3 with o(k) bits of feedback. Perhaps surprisingly, we show the answer is yes! Specifically, we construct a protocol that uses only O(log k) bits of feedback to achieve 1 3 error resilience. We also construct a protocol achieving 1 erasure resilience with O(log k) bits of feedback. We complement our results with a lower bound showing that Ω(log k) bits of feedback are necessary to even have > 1 4 error resilience or > 1 2 erasure resilience, thereby proving Θ(log k) bits of feedback is optimal.

How many rounds of feedback? The second question we address concerns the number of rounds of feedback necessary to achieve 1 3 error resilience. Previous works [Ber64, Mut94, HKV15, SW92] all required