Locally Testable Tree Codes

Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the i-th codeword symbol depends only on the first i message symbols. Codewords should have good tree distance meaning that for any two codewords, starting at the first point of divergence, they should have large Hamming distance.

We investigate whether tree codes can be made to be locally testable. That is, can a tester, which is given oracle access to an alleged codeword w of the tree code, decide whether w is indeed a codeword or far from such, while only reading a sub-linear number of symbols from w.

As the main result of this work, we construct, for any r ≥ 3, a probabilistic tree code that is locally testable using Õ(n 2/r ) queries. The tester accepts any codeword with probability 1 and rejects strings that are δ r -far from the code with high probability, where δ r < 1 degrades with r. Our probabilistic notion of a tree code is a relaxation of the standard notion and allows the encoder to toss random coins. We require that encoded messages are far (in tree distance) from any possible encoding of any other message.