Don Coppersmith and Atri Rudra

On the Robust Testability of Product of Codes

---

Abstract : Tensor product of codes are an elegant way to construct new error correcting codes out of existing ones. Given two error correcting codes (say C₁ and C₂) a codeword in the new code (denoted by C₁ÄC₂) is a matrix such that every column corresponds to a codeword in C₁ and every row corresponds to a codeword in C₂. A natural conjecture that was made couple of years by Ben-Sasson and Sudan was the following. If for a given matrix all columns (and rows) are close\footnote{That is, they differ from some codeword in very few positions.} to some codeword in C_1$(and C₂), then the matrix is close to some codeword in C₁ÄC₂. If true this conjecture will simplify some complicated proofs that show that certain codes are locally testable. P. Valiant showed the existence of codes C₁ and C₂, for which the conjecture is false. However, his argument does not work when C₁= C₂, which is an important special case when using tensor product to build new codes. In this work, we extend Valiant's argument to work for the case when C₁=C₂.

---

Versions

• Electronic Colloquium on Computational Complexity (ECCC) Tech Report TR05-104. 2005.
• Erratum: The results in Section 4 in the version above has a fatal flaw: the distance of the code C in the proof of Theorem 3 is actually 2 and not linear as claimed in the writeup. Thanks to Or Meir for pointing this out. A revised version will be up soon.