Abstract:
Given two codes R,C, their tensor product $R \otimes C$ consists of all matrices whose rows are codewords of R and whose columns are codewords of C. The product $R \otimes C$ is said to be robust if for every matrix M that is far from $R \otimes C$ it holds that the rows and columns of M are far from R and C respectively. Ben-Sasson and Sudan (ECCC TR04-046) have asked under which conditions the product $R \otimes C$ is robust. Paul Valiant (APPROX-RANDOM 2005) gave an example of two linear codes with constant relative distance whose tensor product is not robust. However, one of those codes has a sub-constant rate. We show that this example can be modified so that both codes have constant rate and relative distance.