Leírás
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 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.
Join Zoom Meeting
https://zoom.us/j/92226741265
Meeting ID: 922 2674 1265