pdf icon
Volume 5 (2009) Article 12 pp. 239-255
Tensor Products of Weakly Smooth Codes are Robust
Received: October 2, 2008
Published: December 3, 2009
Download article from ToC site:
[PDF (267K)]    [PS (899K)]    [PS.GZ (228K)]
[Source ZIP]
Keywords: linear code, tensor code, expander code
ACM Classification: E.4
AMS Classification: 68Q99

Abstract: [Plain Text Version]

We continue the study of robustly testable tensor codes and expand the class of base codes that can be used as a starting point for the construction of locally testable codes via robustly testable tensor products. In particular, we show that all unique-neighbor expander codes and all locally correctable codes, when tensored with any other good-distance code, are robustly testable and hence can be used to construct locally testable codes. Previous work by Dinur et al. (2006) required stronger expansion properties to obtain locally testable codes.

Our proofs follow by defining the notion of weakly smooth codes that generalize the smooth codes of Dinur et al. We show that weakly smooth codes are sufficient for constructing robustly testable tensor codes. Using the weaker definition, we are able to expand the family of base codes to include the aforementioned ones.