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 #2 to TR19-147 | 22nd February 2020 07:11

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors

RSS-Feed




Revision #2
Authors: Gil Cohen, Shahar Samocha
Accepted on: 22nd February 2020 07:11
Downloads: 359
Keywords: 


Abstract:

A prior work by Gelles et al. (https://ieeexplore.ieee.org/document/8345651) has already achieved a deterministic capacity approaching interactive coding scheme against adversarial errors, which is the main result claimed in the current submission. We thus withdraw our submission. We are thankful to the anonymous referee of STOC 2020 for point out this overlook. We refer the reader to https://eccc.weizmann.ac.il/report/2020/014/ for a significantly revised version of this submission.


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

Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors





Revision #1
Authors: Gil Cohen, Shahar Samocha
Accepted on: 4th November 2019 20:13
Downloads: 403
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: 468
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.


Comment(s):

Comment #1 to TR19-147 | 23rd February 2020 07:35

Important comment

Authors: Gil Cohen
Accepted on: 23rd February 2020 07:35
Keywords: 


Comment:

The deterministic coding scheme that is devised in this paper, which approaches capacity in the setting of adversarial errors is not the first to appear in the literature as was claimed in this paper. We thank the STOC 2020 referee for pointing out this fact and apologise for this overlook. We refer the reader to https://eccc.weizmann.ac.il/report/2020/014/ for an updated version that refers to the relevant prior result and make the necessary comparison. Furthermore, the revised paper fills a gap in the proof.




ISSN 1433-8092 | Imprint