Pedro Paredes, Princeton University

Abstract

Error-correcting codes provide robust representations of data that can withstand corruption. Over the past 80 years, researchers have made significant strides in designing efficient codes and developing methods for encoding and decoding them. Among the various approaches, one particularly successful strategy has been leveraging the unique properties of expander graphs—sparse yet highly connected graphs.

This talk explores this interesting interplay between error-correcting codes and expander graphs. In the first half, I will highlight key developments in this area. Assuming no prior knowledge of the subject, I will provide a self-contained crash course in coding theory, setting the stage for a discussion of expander codes. I will then delve into recent advancements, including generalizations that lead to locally testable codes and efficient quantum codes.

Motivated by the above, the second half of the talk will focus on the construction of expanders. Specifically, we will examine a body of work dedicated to designing good vertex expanders and unique-neighbor expanders.

See: https://theory.cs.rutgers.edu/theory_seminar