We show an \emph{efficient, deterministic} interactive coding scheme that simulates any interactive protocol under random errors with nearly optimal parameters.
Specifically, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and
a failure probability of~$\exp(-n/ \log n)$, where $n$ is the protocol length and each bit is flipped independently with constant probability $\epsilon$.
Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from~$1$. Furthermore, the best failure probability achievable by an efficient deterministic scheme with constant rate was only quasi-polynomial, i.e., of the form $\exp(- \log^{O(1)} n)$ (Braverman, ITCS 2012). A rate of $1 - \tilde \Theta(\sqrt{H({\epsilon})})$ is essentially optimal (up to poly-logarithmic factors) by a result of Kol and Raz (STOC 2013).
A central contribution in deriving our coding scheme
is a novel code-concatenation scheme, a notion standard in coding theory which we adapt for the interactive setting.
Essential to our concatenation approach is an explicit, efficiently encodable and decodable {\em linear tree code} of length~$n$ that has relative distance $\Omega(1/\log n)$ and
rate approaching~$1$, defined over an $O(\log n)$-bit alphabet.
The fact that our tree code is linear, and in particular can be made {\em systematic}, turns out to play an important role in our concatenation scheme.
We use the above tree code as the ``outer code'' in the concatenation scheme. The necessary deterministic ``inner code'' is achieved by a nontrivial derandomization of the randomized interactive coding scheme of (Haeupler, STOC 2014). This deterministic coding scheme (with {\em exponential} running time,
but applied here to $O(\log n)$ bit blocks) can handle an $\epsilon$ fraction of adversarial errors with a communication rate of $1 - O(\sqrt{H({\epsilon})})$.
Changes in abstract and introduction
We study \emph{efficient, deterministic} interactive coding schemes that simulate any interactive protocol both under random and adversarial errors, and can achieve a constant communication rate independent of the protocol length.
For channels that flip bits independently with probability~$\epsilon<1/2$, our coding scheme achieves a communication rate of $1 - O(\sqrt{H({\epsilon})})$ and a failure probability of~$\exp(-n/ \log n)$ in length $n$ protocols. Prior to our work, all nontrivial deterministic schemes (either efficient or not) had a rate bounded away from~$1$. Furthermore, the best failure probability achievable by an efficient deterministic coding scheme with constant rate was only quasi-polynomial, i.e., of the form $\exp(- \log^{O(1)} n)$ (Braverman, ITCS 2012).
For channels in which an adversary controls the noise pattern our coding scheme can tolerate $\Omega(1/\log n)$ fraction of errors with rate approaching 1. Once more, all previously known nontrivial deterministic schemes (either efficient or not) in the adversarial setting had a rate bounded away from~$1$, and no nontrivial efficient deterministic coding schemes were known with any constant rate.
Essential to both results is an explicit, efficiently encodable and decodable {\em systematic tree code} of length~$n$ that has relative distance $\Omega(1/\log n)$ and rate approaching~$1$, defined over an $O(\log n)$-bit alphabet. No nontrivial tree code (either efficient or not) was known to approach rate~$1$, and no nontrivial distance bound was known for any efficient constant rate tree code. The fact that our tree code is {\em systematic}, turns out to play an important role in obtaining rate $1 - O(\sqrt{H({\epsilon})})$ in the random error model, and approaching rate $1$ in the adversarial error model.
A central contribution in deriving our coding schemes for random and adversarial errors, is a novel code-concatenation scheme, a notion standard in coding theory which we adapt for the interactive setting. We use the above tree code as the ``outer code'' in this concatenation. The necessary deterministic ``inner code'' is achieved by a nontrivial derandomization of the randomized interactive coding scheme of (Haeupler, STOC 2014). This deterministic coding scheme (with {\em exponential} running time, but applied here to $O(\log n)$ bit blocks) can handle an $\epsilon$ fraction of adversarial errors with a communication rate of $1 - O(\sqrt{H({\epsilon})})$.
