COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Good locally testable codes

## Good locally testable codesAdd to your list(s) Download to your calendar using vCal - Alex Lubotzky (Hebrew University of Jerusalem)
- Monday 25 July 2022, 10:00-10:50
- Seminar Room 1, Newton Institute.
If you have a question about this talk, please contact nobody. GR2W02 - Simple groups, representations and applications 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 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. This talk is part of the Isaac Newton Institute Seminar Series series. ## This talk is included in these lists:- All CMS events
- Featured lists
- INI info aggregator
- Isaac Newton Institute Seminar Series
- School of Physical Sciences
- Seminar Room 1, Newton Institute
- bld31
Note that ex-directory lists are not shown. |
## Other listsType the title of a new list here Environment on the Edge Jesus College Graduate Society Graduates' and Fellows' Symposia## Other talksComputer-based trainings as an add-on to the treatment of alcohol addiction: Where are we, how did we get there, and where should we go? Lévy Loewner Evolutions Crack-based assessment and retrofit of concrete members JCTS PRESENTATIONS ‘Cross-Cultural Trade and the Slave Ship the Bonne Société: Baskets of Goods, Diverse Sellers, and Time Pressure on the African Coast’ |