Algebraic Expander Codes - Itzhak Tamo @videosfromIAS
Algebraic Expander Codes - Itzhak Tamo  @videosfromIAS
Uploaded June 2026 | Updated November 2026, 6 hours ago
Computer Science/Discrete Mathematics Seminar II
10:30am|Simonyi 101 and Remote Access
Topic: Algebraic Expander Codes
Speaker: Itzhak Tamo
Affiliation: Tel Aviv University
Date: June 2, 2026

By combining sparse graphs with local constraints, expander codes offer a powerful framework for achieving fast decoding algorithms while maintaining asymptotically good rate and minimum distance. However, the standard constraint-counting arguments only give a positive global rate lower bound when the local rate is r greater than 1/2. Because of this, it was not known how to construct expander codes with a positive rate in the r less than or equal to 1/2 regime. This low-rate regime is highly important for certain modern applications that rely on algebraic local constraints.

In this talk, I will introduce a new way around this barrier: Algebraic Expander Codes. Unlike the standard paradigm, where you pick an expanding graph and a local code independently and glue them together, our approach is purely algebraic. I will show how we can keep Reed-Solomon local constraints while ensuring the global rate stays strictly bounded away from 0 for any fixed local rate between 0 and 1, in particular, in the r less than or equal to 1/2
regime.

The construction is an evaluation code on a single orbit of a non-commutative subgroup of AGL(1,𝔽)
generated by translations and scalings. The expander graph arises naturally as an emergent bipartite coset graph. Finally, I will mention the techniques we used to analyze the construction, such as a new notion of polynomial degree.

Based on joint work with Swastik Kopparty (University of Toronto).
Algebraic Expander Codes - Itzhak TamoSymplectic Excision and Distance Rigidity - Yoel GromanWhat we still don’t know about critical percolation - Tom HutchcroftA Primer on SelfDual Theories - Part 1 - Roland BittlestonHow to Sketch a Learning Algorithm - Sam GunnAdS3 Quantum Gravity via Finite-N Expansions - Wei LiSymplectophagy - Adi DicksteinFrom Fourier Restriction to Number Theory, Combinatorics, & Fractal Geometry III- Dominique MaldagueCreating Periodic Orbits of Reeb Vector Fields in Three Dimensions - Michael HutchingsFloer-Theoretic Entropy of Exact Symplectomorphisms - Joontae KimTaking the cosmic neutrino mass apart: geometry VS growth, and robustness to... - Emmanuel S SchaanIntersections and the Bezout Range - David Urbanik
Institute for Advanced Study |

Algebraic Expander Codes - Itzhak Tamo

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER