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

Formale Metadaten

Titel
Explicit Binary Tree Codes with Poly-Log Size Alphabet
Alternativer Titel
Constructing tree codes
Serientitel
Anzahl der Teile
17
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.