# Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback

arXiv: https://arxiv.org/abs/1501.00624 · HTML: https://mlsanity.com/paper/1501.00624/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jan 2015.

## Built on by (most cited first, 1 of 1)

- [Excuse me, sir? Your language model is leaking (information)](https://mlsanity.com/paper/2401.10360/) (2024)

## Abstract (arXiv)

We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any robust protocol can resist is 1/3. Additionally, we provide a simple and efficient robust protocol that succeeds as long as the fraction of noise is at most 1/3 - ε. Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet. We also consider interactive communication over erasure channels. We provide a protocol that matches the optimal tolerable erasure rate of 1/2 - ε of previous protocols (Franklin et al., CRYPTO '13) but operates in a much simpler and more efficient way. Our protocol works with an alphabet of size 4, in contrast to prior protocols in which the alphabet size grows as epsilon goes to zero. Building on the above algorithm with a fixed alphabet size, we are able to devise a protocol for binary erasure channels that tolerates erasure rates of up to 1/3 - ε.