ScholarLens Back to search
2019•Unpublished venueRequires access

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

Open publisher page 2 citations

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 [1].

About this research paper

What this paper is about

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].

Why it matters

OpenAlex reports 2 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available 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 [1].

Key concepts: Channel capacity, Binary number, Computer science, Capacity planning, Binary symmetric channel, Channel (broadcasting), Binary erasure channel, Mathematics

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
The Interactive Capacity of the Binary Symmetric Channel is at Least 1/40 the Shannon Capacity — Research Paper | ScholarLens