Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with channel capacity:
TR06-151 | 10th December 2006
Prahladh Harsha, Rahul Jain, David McAllester, Jaikumar Radhakrishnan

The communication complexity of correlation

We examine the communication required for generating random variables
remotely. One party Alice will be given a distribution D, and she
has to send a message to Bob, who is then required to generate a
value with distribution exactly D. Alice and Bob are allowed
to share random bits generated ... more >>>

TR13-001 | 2nd January 2013
Gillat Kol, Ran Raz

Interactive Channel Capacity

Revisions: 1

We study the interactive channel capacity of an $\epsilon$-noisy channel. The interactive channel capacity $C(\epsilon)$ is defined as the minimal ratio between the communication complexity of a problem (over a non-noisy channel), and the communication complexity of the same problem over the binary symmetric channel with noise rate $\epsilon$, where ... more >>>

TR19-147 | 31st October 2019
Gil Cohen, Shahar Samocha

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

Revisions: 2 , Comments: 1

We devise a deterministic interactive coding scheme with rate $1-O(\sqrt{\varepsilon\log(1/\varepsilon)})$ against $\varepsilon$-fraction of adversarial errors. The rate we obtain is tight by a result of Kol and Raz (STOC 2013). Prior to this work, deterministic coding schemes for any constant fraction $\varepsilon>0$ of adversarial errors could obtain rate no larger ... more >>>

TR22-117 | 23rd August 2022
Ronen Shaltiel, Jad Silbak

Error Correcting Codes that Achieve BSC Capacity Against Channels that are Poly-Size Circuits

Guruswami and Smith (J. ACM 2016) considered codes for channels that are poly-size circuits which modify at most a $p$-fraction of the bits of the codeword. This class of channels is significantly stronger than Shannon's binary symmetric channel (BSC), but weaker than Hamming's channels which are computationally unbounded.
Guruswami and ... more >>>

ISSN 1433-8092 | Imprint