The Interactive Capacity of the Binary Symmetric Channel is at Least 1/40 the Shannon Capacity
Assaf Ben-Yishai, Young-Han Kim, Or Ordentlich, Ofer Shayevitz · 2019
We define the interactive capacity of the binary symmetric channel (BSC) as the maximal rate for which any interactive protocol can be fully and reliably simulated over a pair of BSC's. We show that this quantity is at least 1/40 of the BSC Shannon capacity, uniformly for all channel crossover probabilities. Our result is based on a public-coin rewind-if-error coding scheme in the spirit of Kol & Raz 2013 [1].