Computer Science/Discrete Mathematics Seminar II

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 > 1/2$. Because of this, it was not known how to construct expander codes with a positive rate in the $r \le 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 \le 1/2$ regime. 

The construction is an evaluation code on a single orbit of a non-commutative subgroup of $AGL(1, \mathbb{F})$ 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).