LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
Algebraic Expander Codes
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

Algebraic Expander Codes

126 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Itzhak Tamo of Tel Aviv University presents this Computer Science/Discrete Mathematics seminar at the Institute for Advanced Study, arguing that a purely algebraic construction can fix a long-standing gap in expander code theory. Standard expander codes, built by gluing a sparse expanding graph to an independently chosen local code, only guarantee a positive rate when the local rate exceeds one half, leaving the low-rate regime needed for algebraic applications unsolved. Tamo shows how keeping Reed-Solomon local constraints while building the code as an evaluation code on a single orbit of a non-commutative subgroup of AGL(1,F), generated by translations and scalings, produces a bipartite coset graph that behaves as the expander itself. He walks through why this keeps the global rate bounded away from zero for any fixed local rate, including the previously inaccessible region at or below one half, and introduces a new notion of polynomial degree used to analyze the construction. The work is joint with Swastik Kopparty of the University of Toronto.

At a glance

Lecture facts

Runtime compared with the other 148 Computer Science lectures
Runtime2 h 6 m
Compared with Computer ScienceLonger than 95%
Source channelInstitute for Advanced Study (YouTube)