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.
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.
Fixed an error in the proof.
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.
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.
