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