Alice and Bob want to run a protocol over a noisy channel, where a certain number of bits are flipped adversarially. Several results take a protocol requiring @math bits of noise-free communication and make it robust over such a channel. In a recent breakthrough result, Haeupler described an algorithm that sends a number of bits that is conjectured to be near optimal in such a model. However, his algorithm critically requires @math knowledge of the number of bits that will be flipped by the adversary. We describe an algorithm requiring no such knowledge. If an adversary flips @math bits, our algorithm sends @math bits in expectation and succeeds with high probability in @math . It does so without any @math knowledge of @math . Assuming a conjectured lower bound by Haeupler, our result is optimal up to logarithmic factors. Our algorithm critically relies on the assumption of a private channel. We show that privacy is necessary when the amount of noise is unknown.
The closest prior work to ours is that of Haeupler @cite_21 . His work assumes a fixed and known adversarial noise rate @math , the fraction of bits flipped by the adversary. Communication efficiency is measured by which is @math divided by the total number of bits sent. Haeupler @cite_21 describes an algorithm that achieves a communication rate of @math , which he conjectures to be optimal. We compare our work to his in .
@cite_21
2026591308
We provide the first capacity approaching coding schemes that robustly simulate any interactive protocol over an adversarial channel that corrupts any @math fraction of the transmitted symbols. Our coding schemes achieve a communication rate of @math over any adversarial channel. This can be improved to @math for random, oblivious, and computationally bounded channels, or if parties have shared randomness unknown to the channel. Surprisingly, these rates exceed the @math interactive channel capacity bound which [Kol and Raz; STOC'13] recently proved for random errors. We conjecture @math and @math to be the optimal rates for their respective settings and therefore to capture the interactive channel capacity for random and adversarial errors. In addition to being very communication efficient, our randomized coding schemes have multiple other advantages. They are computationally efficient, extremely natural, and significantly simpler than prior (non-capacity approaching) schemes. In particular, our protocols do not employ any coding but allow the original protocol to be performed as-is, interspersed only by short exchanges of hash values. When hash values do not match, the parties backtrack. Our approach is, as we feel, by far the simplest and most natural explanation for why and how robust interactive communication in a noisy environment is possible.