Technical Program

Paper Detail

Paper Title Shannon Capacity is Achievable for a Large Class of Interactive Markovian Protocols
Paper IdentifierFR3.R5.1
Authors Assaf Ben-Yishai, Ofer Shayevitz, Tel Aviv University, Israel; Young-Han Kim, University of California, San Diego, Israel
Session Capacity and Upper Bounds
Location Saint Victor, Level 3
Session Time Friday, 12 July, 14:30 - 16:10
Presentation Time Friday, 12 July, 14:30 - 14:50
Manuscript  Click here to download the manuscript
Abstract We address the problem of simulating a binary interactive protocol over a pair of binary symmetric channels with crossover probability $\varepsilon$. We are interested in the achievable rates of reliable simulation, i.e., in characterizing the smallest possible blowup in communications such that a vanishing error probability in the protocol length can be attained. We analyze the family of $M$th-order Markovian protocols in which the transmission at every time depends only on the last $M$ bits of the protocol. For $M=1$ (first-order Markovian) we prove that all protocols can be simulated at Shannon's capacity. For $M>1$ we characterize large classes of protocols that can be simulated at Shannon's capacity.