On Interactive Communication and Uncertainty

Speaker(s) : Anand Kumar Narayanan
Consider two people playing chess remotely across a noisy channel. They devise a coding scheme to communicate their moves where despite a constant fraction of their communications being in error, they infer each other's moves. Since the moves are not known ahead of time, the coding needs to be interactive/online. Tree codes, introduced by Schulman in the 90s, are combinatoric structures essential to error correction for such interactive communication. A tree code is a rooted complete binary tree (of depth n) with a colouring of the vertices (using C colours). This provides a natural way to encode a binary string (of length at most n) to a string of colours of the same length. Error correction is quantified by the distance d; the largest number such that encodings of two distinct strings differ (after their first disagreement) in at least d fraction of places. Schulman proved that there are infinite families of tree codes with both number of colours and distance bounded by positive constants. Yet their explicit construction remains an outstanding open problem. In a major breakthrough last year, Cohen, Haeupler and Schulman [CHS] constructed explicit tree code families of constant distance, but with the number of colours C polylogarithmic in n. A key ingredient in their construction is an uncertainty principle obtained from the combinatoric Lindstrom-Gessel-Viennot lemma.
damien.vergnaud (at)