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 C1 and C2) a codeword in the new code (denoted by C1ÄC2) is a matrix such that every column corresponds to a codeword in C1 and every row corresponds to a codeword in C2. 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 C1$(and C2), then the matrix is close to some codeword in C1ÄC2. If true this conjecture will simplify some complicated proofs that show that certain codes are locally testable. P. Valiant showed the existence of codes C1 and C2, for which the conjecture is false. However, his argument does not work when C1= C2, 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 C1=C2.