Subscribe to Events
The C^3 problem: locally testable codes with constant rate and constant distance
Alex Lubotzky (Hebrew University and IAS)
Location: Hill Center Room 705
Date & time: Wednesday, 17 November 2021 at 3:30PM - 4:30PM
Abstract: An error-correcting code ( LTC) is locally testable 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. Random codes are not LTC !
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. Joint work with I. Dinue, S.Evra, R. Livne and S. Mozes. The talk will be self-contained.