NSF-BSF: AF: Small: Advancing Coding Theory Through the Lens of Pseudorandomness

The goal of this project is to simultaneously advance both the theory of error correcting codes (ECCs) and pseudorandomness by exploring connections between them. ECCs are a fundamental tool to protect data from noise, and the past decade has seen many breakthroughs, both theoretical and practical. Pseudorandomness is the study of deterministic objects that “behave like random objects,” and is a fundamental area in theoretical computer science. Connections between ECCs and pseudorandomness have been noted before, and indeed there is a rich interplay between the two areas. However, the time is right to revisit this connection in light of recent breakthroughs in ECCs. In doing so, this project leads not only to further progress in pseudorandomness by leveraging ECCs, but will also lead to further progress in ECCs, as applications in pseudorandomness highlight important questions in ECCs where current techniques fall short. This project supports graduate and undergraduate education and research, as well as outreach beyond academia. This is a joint NSF-BSF grant; the Israeli PI is Dr. Dean Doron of Ben Gurion University. There are two main thrusts of this research. The first thrust has to do with a notion called “list-recovery,” which has become increasingly important in the study of ECCs. However, recent progress in list-recovery has worked only in a particular parameter regime, which unfortunately is not the parameter regime of interest in pseudorandomness applications. This research investigates list-recovery beyond the parameter regime that is currently understood. Studying list recovery in this parameter regime also has algorithmic applications beyond either coding theory or pseudorandomness. The second thrust has to do with the classical problem of obtaining binary codes with efficient algorithms and the optimal trade-offs between rate (the amount of communication overhead) and distance (a measure of the amount of noise tolerated). This project leverages progress on list-recovery to make progress on this difficult problem. 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.