ECCC-Report TR19-147https://eccc.weizmann.ac.il/report/2019/147Comments and Revisions published for TR19-147en-usMon, 04 Nov 2019 20:13:35 +0200
Revision 1
| Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors |
Gil Cohen,
Shahar Samocha
https://eccc.weizmann.ac.il/report/2019/147#revision1We 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.Mon, 04 Nov 2019 20:13:35 +0200https://eccc.weizmann.ac.il/report/2019/147#revision1
Paper TR19-147
| Capacity-Approaching Deterministic Interactive Coding Schemes Against Adversarial Errors |
Gil Cohen,
Shahar Samocha
https://eccc.weizmann.ac.il/report/2019/147We 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.Sun, 03 Nov 2019 09:09:44 +0200https://eccc.weizmann.ac.il/report/2019/147