Skip to content Skip to navigation
2/14/2018 11:00 am
CoRE 301

Explicit Binary Tree Codes with Polylogarithmic Size Alphabet

Gil Cohen, Princeton University

Organizer(s): Pranjal Awasthi and Shubhangi Saraf


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.


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.