Please note: This seminar will take place in M3 4206 and online.
Rachel
Yun
Zhang,
PhD
student
CSAIL,
Massachusetts
Institute
of
Technology
A code, which is a set of strings called codewords, is locally testable if one can test whether a given word is close to a codeword by reading only a few bits. Locally testable codes have been studied since the 1990s as key ingredients in the construction of probabilistically checkable proofs.
In this talk, I’ll describe a new construction of locally testable codes implemented on high dimensional expanders. It has been known for several years that high dimensional expanders give rise to locally testable codes assuming the existence of a compatible base code. Our main contribution is the construction and analysis of such a base code compatible with the coset complex of Kaufman and Oppenheim.
To attend this seminar in person, please go to M3 4206. You can also attend virtually using Zoom at https://uwaterloo.zoom.us/j/93451507468.