A combinatorial characterization of smooth LTCs and applications1. Issue 2 (19th February 2016)

• Record Type: Journal Article
• Authors: Ben‐Sasson, Eli; Viderman, Michael
• Is Part Of: Random structures & algorithms. Volume 49:Issue 2(2016)
• Page Start: 280
• Page End: 307
• Publication Date: 2016-02-19
• Subjects: linearity testing -- locally testable codes; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20637
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: 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, J. Comput. Syst. Sci. 47 (1993) 549–595) (STOC 1990). Additional connections to the works of (Ben‐Sasson, Harsha, Raskhodnikova, SIAM J. Comput 35 (2005) 1–21) (SICOMP 2005) and of (Lachish, Newman and Shapira, Comput Complex 17 (2008) 70–93) are also discussed. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 280–307, 2016