Assaf Ben-Yishai, Young-Han Kim, Or Ordentlich, and Ofer Shayevitz
IEEE Transactions on Information Theory, vol. 67, no. 12, pp. 7639–7658, December 2021.
Preliminary results appeared in Proceedings of IEEE International Symposium on Information Theory, pp. 2868–2872, Paris, France, July 2019.
The essential interactive capacity of a discrete memoryless channel is defined in this paper as the maximal rate at which the transcript of any interactive protocol can be reliably simulated over the channel, using a deterministic coding scheme. In contrast to other interactive capacity definitions in the literature, this definition makes no assumptions on the order of speakers (which can be adaptive) and does not allow any use of private/public randomness; hence, the essential interactive capacity is a function of the channel model only. It is shown that the essential interactive capacity of any binary memoryless symmetric (BMS) channel is at least 0.0302 its Shannon capacity. To that end, we present a simple coding scheme, based on extended-Hamming codes combined with error detection, that achieves the lower bound in the special case of the binary symmetric channel (BSC). We then adapt the scheme to the entire family of BMS channels, and show that it achieves the same lower bound using extremes of the Bhattacharyya parameter.