
doi: 10.1002/rsa.20637
Summary: 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 \textit{M. Blum} et al. [J. Comput. Syst. Sci. 47, No. 3, 549--595 (1993; Zbl 0795.68131)] (STOC 1990). Additional connections to the works of \textit{E. Ben-Sasson} et al. [SIAM J. Comput. 35, No. 1, 1--21 (2005; Zbl 1086.68045)] (SICOMP 2005) and of \textit{O. Lachish} et al. [Comput. Complexity 17, No. 1, 70--93 (2008; Zbl 1149.68032)] are also discussed.
linearity testing, locally testable codes, Linear codes (general theory)
linearity testing, locally testable codes, Linear codes (general theory)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
