Penn Arts & Sciences Logo

Penn Mathematics Colloquium

Wednesday, November 10, 2021 - 3:45pm

Alex Lubotzky

Hebrew University, Weizmann Institute and IAS


University of Pennsylvania


Tea at 3:15pm in 4E17 DRL. Video Passcode: *F=x18Qh

An error-correcting code is locally testable (LTC)  if there is a random tester that reads only a constant 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 2-dimensional objects seem to be of independent interest.  The lecture will be self-contained.  Ths is joint work with I. Dinue, S.Evra, R. Livne and S. Mozes

Stream Video URL