
Locally Decodable Codes and Representations of Finite Groups
Zeev Dvir of Princeton University gives this Institute for Advanced Study discrete mathematics seminar on the connection between error correcting codes and group theory. Locally decodable codes are built from point sets with many small linear dependencies, such as collinear triples, yet large gaps remain between known constructions and proven lower bounds. Dvir reviews Efremenko's 2008 framework for building such codes from representations of finite groups, then presents a strengthened version of that reduction. Combining it with existing bounds on locally decodable codes, he derives a new result about group representations: an n-dimensional irreducible representation that sends some element away from the identity must move it a distance of at least n over the log of the group's order, measured in rank metric, and shows this bound is tight. The talk is aimed at a specialist audience familiar with coding theory and representation theory.