Seminar Details

The notion of robust local testability has played a key role in several developments in classical and quantum coding theory as well as complexity theory, such as constructions of Probabilistically Checkable Proofs (PCP) in the 1990s, and recent breakthroughs on Locally Testable Codes (LTCs) and Quantum Low Density Parity Check (qLDPC) codes. Despite its importance, robust local testability was established for only a limited number of code families, such as Reed–Solomon codes, random codes, and certain LDPC codes.

In this talk, we will discuss this notion of robust local testability and focus on Reed-Solomon and Algebraic-Geometric (AG) codes. AG codes are natural generalizations of Reed-Solomon (RS) codes that allow longer block lengths over fixed alphabets and good distance/rate tradeoffs.

I’ll talk about a recent result showing that tensor products of constant rate AG codes are robustly testable. This generalizes the robust testability of RS codes and provides new applications toward constructions of qLDPC codes. I’ll discuss a geometric perspective on tensor products of RS/AG codes. We will see how this geometric perspective leads to a generalization of the bivariate divisibility lemma of Polishchuk-Spielman – the key statement for robust testability of RS codes. 

This is joint work with Sumegha Garg.