Seminar:
Colloquium
Event time:
Wednesday, February 9, 2022 - 4:15pm
Speaker:
Alex Lubotzky
Speaker affiliation:
Hebrew University/Yale University
Event description:
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 problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance. Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind.
We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes. These 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 Howard Garland ( 1972) on the cohomology of quotients of the Bruhat-Tits buildings of p-adic Lie group has led to this construction ( even though, it is not used at the end). Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes. The lecture will also serve as a preview for a crash course on that topic which will start the day after.
Special note:
Colloquium supported in part by the Mrs. Hepsa Ely Silliman Memorial Fund.