Seminar Details

Folded Reed-Solomon (FRS) codes are a well-studied family of codes, known for achieving list decoding capacity. There has been a recent flurry of exciting results that have sharpened our combinatorial understanding of list sizes of FRS codes at capacity -- up to a constant factor, they are as small as possible!
In this talk, we will see improved deterministic and randomized algorithms for list decoding FRS codes at capacity. This shortens the gap between our new combinatorial understanding and our algorithmic understanding of FRS codes. We will begin from the ground up (what is a code? list decoding? capacity?) and, on the way to our main results, explore how to compute the intersection of affine subspaces of $mathbb{F}_q^n$ and Hamming balls (and, perhaps, how a hierarchy of expander graphs plays a role in doing this efficiently).
Based on joint work with Mursalin Habib and Shashank Srivastava.