In a ground-breaking paper published in 1993, Schulman introduced the powerful notion of (what we shall call) ``good tree codes''. Good tree codes are deterministic online encoding procedures with strong distance properties. Schulman shows that these strong properties allow one to solve the fundamental problem of interactive communication over a noisy (or adversarial) channel, optimally up to constant factors. Unfortunately, constructions of good tree codes have remained elusive. Even high probability randomized constructions of good tree codes are not known, let alone explicit constructions, even under computational assumptions.
In this work, motivated by the difficulties of obtaining explicit good tree codes, we introduce a new notion of goodness for tree codes. We define the notion of a potent tree code, which relaxes key requirements of good tree codes. Nevertheless, we show that they still enable the fundamental applications of good tree codes: obtaining constant-overhead reliable interactive communication over noisy and adversarial channels.
In contrast to good tree codes, however, we show a high probability existence argument for potent tree codes. Furthermore, using pseudorandomness, we show a high probability explicit construction of potent tree codes using only a polynomially bounded amount of randomness, under the assumption that we have an explicit one-way function. We believe that the relaxed nature of potent tree codes may make them more amenable to future attempts to obtain fully explicit constructions.
Joint work with Ran Gelles.
Copyright. All Rights Reserved.