Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR22-179 | 16th December 2022 06:01

Round-vs-Resilience Tradeoffs for Binary Feedback Channels


Authors: Mark Braverman, Klim Efremenko, Gillat Kol, Raghuvansh Saxena, Zhijun Zhang
Publication: 16th December 2022 06:08
Downloads: 77


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.

ISSN 1433-8092 | Imprint