In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. This protocol fails over a noisy channel with only exponentially small probability. However, this scheme is not computationally {\em efficient}: the running time to construct a good distance {\em tree code} (and perform encoding and decoding), which is the basis for the simulation, requires time exponential in the length of the protocol. Here, we give a computationally efficient simulation that achieves constant slow-down, and fails over a noisy channel with only polynomially small probability. Our protocol is deterministic and is based on a new type of code, which we call a {\em local tree code}. These codes can be regarded as an embedding of a tree code into a high-girth expander, so that locally these codes resemble tree codes, but are concisely represented and admit efficient encoding and decoding schemes (that succeed with high probability when communicating over a noisy channel).

In 1992, Schulman proved a coding theorem for interactive communication and demonstrated that interactive communication protocols can be made robust to noise with only a constant slow-down (for a sufficiently small error rate) through a black-box reduction. However, this scheme is not computationally {\em efficient}: the running time to construct a good distance {\em tree code} (and perform encoding and decoding), which is the basis for the simulation, requires time exponential in the length of the protocol. Here, we give the first computationally efficient simulation that achieves constant slow-down, and is robust to noise. In fact, our protocol is deterministic and is in part based on recent progress on constructive proofs of the general Lov\'asz Local Lemma. Prior to this work, the only known {\em efficient} simulation was the naive one based on retransmitting each bit in order to achieve reliability. Our approach is based on a new type of code, which we call a {\em local tree code}. These codes can be regarded as an embedding of a tree code into a high-girth expander, so that locally these codes resemble tree codes, but are concisely represented and admit efficient encoding and decoding schemes (that succeed with high probability when communicating over a noisy channel).