Explicit binary tree codes with polylogarithmic size alphabet

Gil Cohen, Bernhard Haeupler, Leonard J. Schulman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

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 poly(log 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). 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.

Original languageEnglish (US)
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages1074-1087
Number of pages14
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018Jun 29 2018

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period6/25/186/29/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Explicit constructions
  • Sparse polynomials
  • Tree codes

Fingerprint Dive into the research topics of 'Explicit binary tree codes with polylogarithmic size alphabet'. Together they form a unique fingerprint.

Cite this