Combinatorics Seminar
When: Sunday, December 11, 10am
Where: Schreiber 309
Speaker: Tali Kaufman, Bar Ilan University
Title: Locally Testable Codes and Expanders
Abstract:
Expanders and Error correcting codes are two celebrated notions,
coupled together, e.g., in the seminal work on Expander Codes by
Sipser and Spielman that yields some of the best codes. Recently,
there is a growing interest in codes admitting algorithms that run
in constant time, e.g., codes for which it is possible
to distinguish in constant time between codewords and vectors far
from the code. Such codes are known as locally testable codes
(LTCs).
It is known that Expander Codes based on best expanders can NOT
yield LTCs, so it seems that expansion is somewhat contradicting to
the notion of LTCs. We show that, nevertheless, the graph associated
with an LTC must be essentially an expander. Namely, this graph is
a small set expander and it can be decomposed into constant many
expander graphs on which the induced codes are approximately LTCs.
Based on a joint work with Irit Dinur.