An error correcting code is said to be locally testable if there is a test that can check whether a given string is a codeword, 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 several constructions of LTCs have been suggested.
While the best known construction of LTCs by Ben-Sasson and Sudan (STOC 2005) and Dinur (STOC 2006) achieves very efficient parameters, it relies on heavy algebraic tools and on PCP machinery. In this work we present a new and arguably simpler construction of LTCs that is purely combinatorial, does not rely on PCP machinery and matches the parameters of the previously known construction. However, unlike the latter construction, our construction is not entirely explicit.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, October 2007.
Available: the thesis (in PDF file).
See additional works:
Back to Oded Goldreich's homepage.