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










