The Taub Faculty of Computer Science Events and Talks
Or Meir, (Weizmann Institute of Science)
Sunday, 06.07.2008, 11:00
An error correcting code is said to be locally testable if there is a
can check whether a given string is a codeword of the code, or rather
the code, by reading only a constant number of symbols of the string.
Testable Codes (LTCs) were first explicitly studied by Goldreich and
Sudan (J. ACM 53(4)) and
since then several constructions of LTCs were suggested.
While the best known construction of LTCs achieves very efficient
parameters, it relies heavily on algebraic tools and on PCP machinery.
We present a new and arguably simpler construction of LTCs that is
purely combinatorial and does not rely on PCP machinery. Finally, our
construction matches the parameters of the best known construction.