Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-159 | 20th November 2012 05:08

A Combinatorial Characterization of smooth LTCs and Applications


Authors: Eli Ben-Sasson, Michael Viderman
Publication: 20th November 2012 05:08
Downloads: 3659


The study of locally testable codes (LTCs) has benefited from a number of nontrivial constructions discovered in recent years. Yet we still lack a good understanding of what makes a linear error correcting code locally testable and as a result we do not know what is the rate-limit of LTCs and whether asymptotically good linear LTCs with constant query complexity exist.

In this paper we provide a combinatorial characterization of smooth locally testable codes, which are locally testable codes whose associated tester queries every bit of the tested word with equal probability. Our main contribution is a combinatorial property defined on the Tanner graph associated with the code tester ("well-structured tester"). We show that a family of codes is smoothly locally testable if and only if it has a well-structured tester.

As a case study we show that the standard tester for the Hadamard code is "well-structured", giving an alternative proof of the local testability of the Hadamard code, originally proved by [Blum, Luby, Rubinfeld, STOC 1990]. Additional connections to the works of [Ben-Sasson, Harsha, Raskhodnikova, SICOMP 2005] and of [Lachish, Newman and Shapira, Computational Complexity 2008] are also discussed.

ISSN 1433-8092 | Imprint