Cohen, Haeupler, and Schulman: Explicit Binary Tree-Codes & Cancellations

The high-dimensional conference in Jerusalem is running with many exciting talks (and they are videotaped), and today in Tel Aviv there is a conference on Optimization and Discrete Geometry : Theory and Practice.

Today in Jerusalem, Leonard Schulman talked (video available!) about a  recent breakthrough by  Gil Cohen, Bernhard Haeupler, and Leonard Schulman in the recent paper Explicit Binary Tree Codes with Polylogarithmic Size Alphabet.

Tree codes

Tree codes are extremely important objects invented by Leonard Schulman in 1992-1996. You can read about it in Wigderson’s book  Mathematics and Computation  (see also this post) in a whole section about  Error-correction of interactive communication, a theory pioneered by Leonard. Finding explicit good (linear distance, finite alphabet) tree codes is a very important problem.

(From the introduction of the new paper) “A tree code consists of a complete rooted binary tree (either infinite or of finite depth ) in which each edge is labeled by a symbol from an alphabet . There is a natural one-to-one mapping assigning each binary string to a path starting at the root, where simply indicates which child is taken in each of the steps. For a tree code, such a path naturally maps to a string over the alphabet , which is formed by concatenating the symbols along the path. This way a tree code encodes any binary string into an equally long string over . This encoding has an online characteristic because the encoding of any prefix does not depend on later symbols. In particular, any two distinct strings that agree in their first symbols also have encodings that agree in their first symbols. A tree code is said to achieve distance  if the encodings of any two strings differ in at least a -fraction of the positions after their first disagreement. The rate of a tree code is . A tree code is said to be asymptotically good if it achieves both constant distance   and a constant rate, namely, the alphabet size is .”

The abstract:

“This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size.

For every constant 1 we give an explicit binary tree code with distance  and alphabet size , where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size .

As part of the analysis, we prove a bound on the number of positive integer roots a real polynomial can have in terms of its sparsity with respect to the Newton basis – a result of independent interest.”

Problems on Exponential sums

A few years ago Cris Moore and Leonard Schulman proposed an explicit constructions for good tree codes in the paper Tree codes and a conjecture on exponential sums. The construction depends on still open conjectures on new types of exponential sums.

A paper by Leonard and me on polynomials with massive cancellations.

So let me use this opportunity to advertize a paper by Leonard and me Quasi-random multilinear polynomials which was just accepted for publication in the Israel Journal of Mathematics. Unexpected cancellation is always a very interesting phenomenon that we cherish and wish to understand. For example, we expect that the sum of the Mobius function for the first n integers cancels almost like that of a random walk. Depending on the meaning of “almost” this is the (known) prime number theorem, the (conjectured) Riemann hypothesis, or simply false, respectively.

A little less famous example  (which I personally like) is the paper by Nikola Djokic  an upper bound on the sum of signs of permutations with a condition on their prefix sets solving a problem by J. Feldman, H. Knorrer, and E. Trubowitz.

Our starting point is the determinant: It is a polynomial of degree of variables and no matter what values you assign to the variables you have a massive cancellation of almost a random-walk type. There are terms and for any assignment the value is smaller than which is .  We were interested in the question of finding other such polynomials.