# Technical Program

## Paper Detail

Paper Title Shannon Capacity is Achievable for a Large Class of Interactive Markovian Protocols FR3.R5.1 Assaf Ben-Yishai, Ofer Shayevitz, Tel Aviv University, Israel; Young-Han Kim, University of California, San Diego, Israel Capacity and Upper Bounds Saint Victor, Level 3 Friday, 12 July, 14:30 - 16:10 Friday, 12 July, 14:30 - 14:50 Click here to download the manuscript 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.