  We study the fundamental problem of reliable interactive communication over a
noisy channel. In a breakthrough sequence of papers published in 1992 and 1993,
Schulman gave non-constructive proofs of the existence of general methods to
emulate any two-party interactive protocol such that: (1) the emulation
protocol takes a constant-factor longer than the original protocol, and (2) if
the emulation protocol is executed over a noisy channel, then the probability
that the emulation protocol fails is exponentially small in the total length of
the protocol. Unfortunately, Schulman's emulation procedures either only work
in a model with a large amount of shared randomness, or are non-constructive in
that they rely on the existence of good tree codes. The only known proofs of
the existence of good tree codes are non-constructive, and finding an explicit
construction remains an important open problem. Indeed, randomly generated tree
codes are not good tree codes with overwhelming probability.
  In this work, we revisit the problem of reliable interactive communication,
and obtain the following results: We introduce a new notion of goodness for a
tree code, and define the notion of a potent tree code. We believe that this
notion is of independent interest. We prove the correctness of an explicit
emulation procedure based on any potent tree code. We show that a randomly
generated tree code (with suitable constant alphabet size) is a potent tree
code with overwhelming probability. Furthermore we are able to partially
derandomize this result using only O(n) random bits, where $n$ is the depth of
the tree.
  These results allow us to obtain the first fully explicit emulation procedure
for reliable interactive communication over noisy channels with a constant
communication overhead, and exponentially small failure probability.
