The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable

Webpage for a paper by Oded Goldreich and Or Meir


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.

Material available on-line


Back to either Oded Goldreich's homepage. or general list of papers.