We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Explicit Binary Tree Codes with Poly-Log Size Alphabet

Formal Metadata

Title
Explicit Binary Tree Codes with Poly-Log Size Alphabet
Alternative Title
Constructing tree codes
Title of Series
Number of Parts
17
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
In this talk, we consider the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. We present 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 the Newton basis - a result of independent interest.