Technical Program

Paper Detail

Paper Title The Interactive Capacity of the Binary Symmetric Channel is at Least 1/40 the Shannon Capacity
Paper IdentifierFR3.R5.2
Authors Assaf Ben-Yishai, Tel Aviv University, Israel; Young-Han Kim, University of California, San Diego, United States; Or Ordentlich, Hebrew University of Jerusalem, Israel; Ofer Shayevitz, Tel Aviv University, 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:50 - 15:10
Manuscript  Click here to download the manuscript
Abstract 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.