Combinatorial Construction of Locally Testable Codes
Or Meir · SIAM Journal on Computing · 2008
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. While the best known construction of locally testable codes (LTCs) by Ben-Sasson and Sudan [SIAM J. Comput., 38 (2008), pp. 551–607] and Dinur [J. ACM, 54 (2007), article 12] achieves very efficient parameters, it relies heavily on algebraic tools and on probabilistically checkable proof (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.