Explicit binary tree codes with polylogarithmic size alphabet

Gil Cohen; Bernhard Haeupler; Leonard J. Schulman

doi:10.1145/3188745.3188928

Explicit binary tree codes with polylogarithmic size alphabet

Gil Cohen, Bernhard Haeupler, Leonard J. Schulman

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 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 language	English (US)
Title of host publication	STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
Editors	Monika Henzinger, David Kempe, Ilias Diakonikolas
Publisher	Association for Computing Machinery
Pages	1074-1087
Number of pages	14
ISBN (Electronic)	9781450355599
DOIs	https://doi.org/10.1145/3188745.3188928
State	Published - Jun 20 2018
Event	50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States Duration: Jun 25 2018 → Jun 29 2018

Publication series

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

Other

Other	50th Annual ACM Symposium on Theory of Computing, STOC 2018
Country/Territory	United States
City	Los Angeles
Period	6/25/18 → 6/29/18

All Science Journal Classification (ASJC) codes

Software

Keywords

Explicit constructions
Sparse polynomials
Tree codes

Access to Document

10.1145/3188745.3188928

Cite this

Cohen, G., Haeupler, B., & Schulman, L. J. (2018). Explicit binary tree codes with polylogarithmic size alphabet. In M. Henzinger, D. Kempe, & I. Diakonikolas (Eds.), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (pp. 1074-1087). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3188745.3188928

Cohen, Gil ; Haeupler, Bernhard ; Schulman, Leonard J. / Explicit binary tree codes with polylogarithmic size alphabet. STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. editor / Monika Henzinger ; David Kempe ; Ilias Diakonikolas. Association for Computing Machinery, 2018. pp. 1074-1087 (Proceedings of the Annual ACM Symposium on Theory of Computing).

@inproceedings{79112ecd62574d3689d9139d1ad25928,

title = "Explicit binary tree codes with polylogarithmic size alphabet",

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.",

keywords = "Explicit constructions, Sparse polynomials, Tree codes",

author = "Gil Cohen and Bernhard Haeupler and Schulman, {Leonard J.}",

note = "Publisher Copyright: {\textcopyright} 2018 Association for Computing Machinery.; 50th Annual ACM Symposium on Theory of Computing, STOC 2018 ; Conference date: 25-06-2018 Through 29-06-2018",

year = "2018",

month = jun,

day = "20",

doi = "10.1145/3188745.3188928",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "1074--1087",

editor = "Monika Henzinger and David Kempe and Ilias Diakonikolas",

booktitle = "STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing",

}

Cohen, G, Haeupler, B & Schulman, LJ 2018, Explicit binary tree codes with polylogarithmic size alphabet. in M Henzinger, D Kempe & I Diakonikolas (eds), STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Proceedings of the Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, pp. 1074-1087, 50th Annual ACM Symposium on Theory of Computing, STOC 2018, Los Angeles, United States, 6/25/18. https://doi.org/10.1145/3188745.3188928

Explicit binary tree codes with polylogarithmic size alphabet. / Cohen, Gil; Haeupler, Bernhard; Schulman, Leonard J.
STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. ed. / Monika Henzinger; David Kempe; Ilias Diakonikolas. Association for Computing Machinery, 2018. p. 1074-1087 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Explicit binary tree codes with polylogarithmic size alphabet

AU - Cohen, Gil

AU - Haeupler, Bernhard

AU - Schulman, Leonard J.

PY - 2018/6/20

Y1 - 2018/6/20

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

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

KW - Explicit constructions

KW - Sparse polynomials

KW - Tree codes

UR - http://www.scopus.com/inward/record.url?scp=85049922797&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85049922797&partnerID=8YFLogxK

U2 - 10.1145/3188745.3188928

DO - 10.1145/3188745.3188928

M3 - Conference contribution

AN - SCOPUS:85049922797

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1074

EP - 1087

BT - STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

A2 - Henzinger, Monika

A2 - Kempe, David

A2 - Diakonikolas, Ilias

PB - Association for Computing Machinery

T2 - 50th Annual ACM Symposium on Theory of Computing, STOC 2018

Y2 - 25 June 2018 through 29 June 2018

ER -

Cohen G, Haeupler B, Schulman LJ. Explicit binary tree codes with polylogarithmic size alphabet. In Henzinger M, Kempe D, Diakonikolas I, editors, STOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2018. p. 1074-1087. (Proceedings of the Annual ACM Symposium on Theory of Computing). doi: 10.1145/3188745.3188928

Explicit binary tree codes with polylogarithmic size alphabet

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this