Title: Locally tested good error correcting codes
Abstract: An error-correcting code is locally testable (LTC) if there is a random tester that reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it.
A long-standing question is whether there exists such a code that also meets the golden standards of coding theory: constant rate and constant distance. Unlike the traditional setting in coding theory, random codes are not LTC, so this problem presents a new kind of challenge.
We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes. These objects seem to be of independent group-theoretic interest. The codes built on them are 2-dimensional versions of the expander codes constructed by Sipser and Spielman (1996).
The main result and lecture will be self-contained. But we hope also to explain how the seminal work of Howard Garland ( 1972) on the cohomology of quotients of the Bruhat-Tits buildings of p-adic Lie groups has led to this construction ( even though it is not used at the end).
Based on joint work with Dinur, Evra, Livne, and Mozes.