Alex Lubotzky (Hebrew Univ / Weizmann Institute / IAS)
Title: The C^3 problem: error-correcting codes with a constant rate, constant distance, and constant locality.
听
Abstract: 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.
听