Alex Lubotzky: Good locally testable codes

Date of publication: 10. 5. 2022

Discrete mathematics seminar

Tuesday

May

Time:

19:00

Location:

Na daljavo

Zoom link

ID: 871 9332 0713 – Password: 653250

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.

Dear colleagues,

The organizers of the Algebraic Graph Theory International Webinar would like to invite you to another presentation, this time on May 10, 2022, at 7pm Central European Summer Time (= 5pm UTC), delivered by Alex Lubotzky.

Title: Good locally testable 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 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 Zoom link:

https://cuaieed-unam.zoom.us/j/87193320713?pwd=cHpiWUtYWlUvWHZjdGZteSt1QmZ5UT09 Meeting ID: 871 9332 0713

Passcode: 653250

Further details may be found at http://euler.doa.fmph.uniba.sk/AGTIW.html where you can also find the slides and recordings for our previous presentations. Also, if you wish to advertise an AGT friendly conference on this page, please send us the link.

Hoping to see you at the webinar, and wishing you all the best.

Isabel Hubard, Robert Jajcay and Primož Potočnik