Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR07-115 | 23rd February 2023 17:17

Combinatorial Construction of Locally Testable Codes

RSS-Feed




Revision #1
Authors: Or Meir
Accepted on: 23rd February 2023 17:17
Downloads: 109
Keywords: 


Abstract:

An error correcting code is said to be locally testable if there is a test that checks 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 systematically 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 (J. ACM 54(3)) achieves very efficient parameters, it relies heavily on 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 best known construction. However, unlike the latter construction, our construction is not entirely explicit.



Changes to previous version:

An updated version.


Paper:

TR07-115 | 19th November 2007 00:00

Combinatorial Construction of Locally Testable Codes





TR07-115
Authors: Or Meir
Publication: 19th November 2007 11:07
Downloads: 3164
Keywords: 


Abstract:

An error correcting code is said to be locally testable if there is a test that checks 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 systematically 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 (J. ACM 54(3)) achieves very efficient parameters, it relies heavily on 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 best known construction. However, unlike the latter construction, our construction is not entirely explicit.



ISSN 1433-8092 | Imprint