Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-147 | 4th November 2019 20:13

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

RSS-Feed




Revision #1
Authors: Gil Cohen, Shahar Samocha
Accepted on: 4th November 2019 20:13
Downloads: 57
Keywords: 


Abstract:

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 than $1/2$. Achieving higher rate was obtained either using probabilistic coding schemes by Haeupler (FOCS 2014) or otherwise assumed weaker error models such as binary symmetric channels, erasure channels or feedback channels.



Changes to previous version:

Fixed an error in the proof.


Paper:

TR19-147 | 31st October 2019 12:27

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors





TR19-147
Authors: Gil Cohen, Shahar Samocha
Publication: 3rd November 2019 09:09
Downloads: 45
Keywords: 


Abstract:

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 than $1/2$. Achieving higher rate was obtained either using probabilistic coding schemes by Haeupler (FOCS 2014) or otherwise assumed weaker error models such as binary symmetric channels, erasure channels or feedback channels.



ISSN 1433-8092 | Imprint