
Algebraic Expander Codes
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.