Haifa University - Dept. of CS Theory Seminar
Speaker : Or Meir, Weizmann.
Title: "Combinatorial Construction of Locally Testable Codes"
Date: Thursday, Dec. 20.
Place: Haifa U. Education Building, room 570.
Time: 12:15 - 13:30
Abstract:
An error correcting code is said to be \sf{locally testable} if there is a
test that can check whether a given string is a codeword of the code, or
rather far from the code, by reading only a constant number of symbols of
the string. Locally Testable Codes (LTCs) were first explicitly studied by
Goldreich and Sudan (J. ACM 53(4)) and since then few constructions of LTCs
were suggested.
LTCs are connected with Probabilistically Checkable Proofs (PCPs) and can
be seen as the "combinatorial counterparts" of PCPs. Since they are simpler
objects then PCPs, one might expect that constructing LTCs would be easier
than constructing PCPs. However, all the known constructions either use PCP
as a building block, or imply directly the existence of a PCP.
In this work we present a new and simpler construction of LTCs that seems
to be strictly weaker than PCP. Another important feature of our
construction is that it is purely combinatorial, while previous
constructions were very algebraic. Finally, our construction matches the
parameters of the best known construction of LTCs by Ben-Sasson and Sudan
(STOC 2005) and Dinur (STOC 2006).