CAREER: Codes and Pseudorandom Structures

In 1948, Claude Shannon identified error correcting codes as the key tools which enable communication over a noisy channel. Codes have been extensively studied ever since, resulting in remarkable optimizations, generalizations and diverse applications. Important work in the 1990s showcased code constructions based on "pseudorandom" objects in discrete mathematics. This connection between pseudorandomness and coding theory has subsequently evolved to the point that today it is routine for advances in coding theory to follow from results in pseudorandomness. This proposal will explore the interplay between pseudorandomness and coding theory from several angles with the intention of constructing new codes and deepening our understanding of pseudorandomness. Work from this proposal will result in publicly available educational materials including new course materials and technical video streams which will benefit experts, students, and enthusiasts alike. In more detail, we aim to improve recent code constructions based on expander graphs. One recent line of work has used expander graphs to design error correcting codes which approach the Gilbert-Varshamov bound, the optimal tradeoff possible between two important code parameters: distance and rate. A second recent line of work has used "high dimensional" versions of expander graphs to give locally testable codes which have constant rate, soundness and query complexity. Interestingly, both of these codes can be viewed as heavily derandomized versions of the same basic object: the XOR code. Surprisingly, though the XOR code is very simple, many of its fundamental properties are not well understood. We will explore different ways to improve these recent codes by answering questions about the XOR code. For example, is the XOR code combinatorially list decodable beyond the Johnson bound? Is the "natural" 3-query local test on the XOR code sound? Affirmative answers to these basic questions could translate to high-impact advances. This proposal will aim to answer these and other questions in order to improve modern state-of-the-art codes. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.