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*_{1} and
*C*_{2}) a codeword in the new code (denoted by
*C*_{1}Ä*C*_{2}) is a matrix
such that every column corresponds to a codeword in *C*_{1} and every
row corresponds to a codeword in *C*_{2}. 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*_{2}), then the
matrix is close to some codeword in *C*_{1}Ä*C*_{2}. 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*_{1} and *C*_{2}, for which the conjecture
is
false. However, his argument does not work when *C*_{1}=
*C*_{2}, 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*_{1}=*C*_{2}.

** Versions**