We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A combinatorial characterization of smooth LTCs and applications.
- Authors
Ben‐Sasson, Eli; Viderman, Michael
- 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
- Subjects
ERROR-correcting codes; PROBABILITY theory; COMBINATORIAL probabilities; HADAMARD codes; HAMMING distance
- Publication
Random Structures & Algorithms, 2016, Vol 49, Issue 2, p280
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20637