Tree codes
summary
Open problem for 30+ years: construct a constant alphabet tree code with constant relative distance δ>0 and poly(n) time per edge (strongly explicit). Known facts: 2 or 3 colors provably fail, 4 colors exist, and explicit constructions with alphabet size polylog n come from Newton-basis evaluation (Reed‑Solomon style), a sparsity-vs-zeros lemma, and recursive tensoring that trades t for √t. The paper builds working polylog‑alphabet codes; a conjectured nonvanishing of certain linearized‑polynomial determinants would yield the desired constant‑alphabet solution.
AI-written summary · about
chapters (9)
- 0:00Introduction and announcements
- 0:48Motivation for tree codes
- 4:47Definition and basic properties
- 10:43Applications and open problems
- 14:03Existing construction techniques
- 18:33Evaluation code construction
- 28:55Recursion and bit complexity
- 34:48Tensoring and reduction
- 38:35Conjectures and conclusions
related talks
01h 02mTree PCPs
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
01h 09mWhen Cryptography Meets Modern Channel Coding
58mBosonic (And Other) Codes With Interesting Logical Gate Sets
41mHigh-Rate Fair-Density Parity-Check Codes
01h 00mError-Correcting Codes That Enable Efficient SNARKs
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
19mError Correcting Codes for Uncompressed Messages