In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is ``continuous'', i.e., after every utilization of the channel, the sender gets the symbol received by the receiver. While this assumption is natural in some settings, in other settings it may be unreasonable or too costly to maintain.
In this work, we initiate the study of round-restricted feedback channels, where the number $r$ of feedback rounds is possibly much smaller than the number of utilizations of the channel. Error correcting codes for such channels are protocols where the sender can ask for feedback at most $r$ times, and, upon a feedback request, it obtains all the symbols received since its last feedback request. We design such error correcting protocols for both the adversarial binary erasure channel and for the adversarial binary corruption (bit flip) channel. For the erasure channel, we give an exact characterization of the round-vs-resilience tradeoff by designing a (constant rate) protocol with $r$ feedback rounds, for every $r$, and proving that its noise resilience is optimal.
Designing such error correcting protocols for the corruption channel is substantially more involved. We show that obtaining the optimal resilience, even with one feedback round ($r=1$), requires settling (proving or disproving) a new, seemingly unrelated, ``clean'' combinatorial conjecture, about the maximum cut in weighted graphs versus the ``imbalance'' of an average cut. Specifically, we prove an upper bound on the optimal resilience (impossibility result), and show that the existence of a matching lower bound (a protocol) is equivalent to the correctness of our conjecture.
Added Section 11 and minor revisions.
In a celebrated result from the $60$'s, Berlekamp showed that feedback can be used to increase the maximum fraction of adversarial noise that can be tolerated by binary error correcting codes from $1/4$ to $1/3$. However, his result relies on the assumption that feedback is "continuous", i.e., after every utilization of the channel, the sender gets the symbol received by the receiver. While this assumption is natural in some settings, in other settings it may be unreasonable or too costly to maintain.
In this work, we initiate the study of round-restricted feedback channels, where the number $r$ of feedback rounds is possibly much smaller than the number of utilizations of the channel. Error correcting codes for such channels are protocols where the sender can ask for feedback at most $r$ times, and, upon a feedback request, it obtains all the symbols received since its last feedback request.
We design such error correcting protocols for both the adversarial binary erasure channel and for the adversarial binary corruption (bit flip) channel. For the erasure channel, we give an exact characterization of the round-vs-resilience tradeoff by designing a (constant rate) protocol with $r$ feedback rounds, for every $r$, and proving that the noise resilience it achieves is optimal. For the corruption channel, we give a protocol with one feedback round and prove that its optimality hinges on a "clean" combinatorial conjecture about the maximum cut in weighted graphs.
