View article

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 …