Colloquium: Tuesday Jan. 21, 2025. Speaker: Alex Lubotzky (Weizmann). Title: “Good locally testable codes”.
Speaker: Alex Lubotzky (Weizmann)
Place: Room 614, Education and Sciences Building, University of Haifa
Date and Time: January 21, 2025, 14:00-15:00
Title: Good locally testable codes
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 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 I. Dinur, S. Evra, R. Livne, and S. Mozes.
Zoom link: https://us02web.zoom.us/j/87282501214?pwd=gnoO4TOG9LKBQJrfQ89Od7nUkoy0S3.1
Meeting ID: 872 8250 1214