Skip to content Skip to navigation

Seminar: Explicit Binary Tree Codes with Polylogarithmic Size Alphabet


In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We give an explicit binary tree code with constant distance and alphabet size polylog(n), 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 poly(n). For analyzing our construction, we prove a bound on the number of integral roots a real polynomial can have in terms of its sparsity with respect to a suitable basis--a result of independent interest.

Joint work with Bernhard Haeupler and Leonard Schulman.

Gil Cohen

My name is Gil Cohen. I'm a research instructor at Princeton University. I spent a lovely year at Caltech as a postdoc and completed my Ph.D. at weizmann under the inspiring guidance of Ran Raz. I'm very excited to join Tel Aviv University in Fall '18!

My interests lie mostly in theoretical computer science with a focus on pseudorandomness, explicit constructions, and computational complexity. In general, I am fascinated by the role that randomness plays in computation and in mathematics.

CoRE 301
Event Date: 
02/14/2018 - 11:00am
Pranjal Awasthi and Shubhangi Saraf
Event Type: 
Princeton University