Abstract:
Given linear 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. During the last few years, few important families of tensor products were shown to be robust, and a counter-example of a product that is not robust was also given. However, a precise characterization of codes whose tensor product is robust remains unknown. In this note we highlight a common theme in the above papers, which we call ``The Rectangle Method''. In short, we observe that all proofs of robustness in the above papers are done by constructing a ``rectangle'', while in the counterexample no such rectangle can be constructed. We then show that a rectangle can be constructed if and only if the tensor product is robust, and therefore the proof strategy of constructing a rectangle is complete.

Abstract:
Given linear 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. During the last few years, few important families of tensor products were shown to be robust, and a counter-example of a product that is not robust was also given. However, a precise characterization of codes whose tensor product is robust remains unknown. In this note we highlight a common theme in the above papers, which we call "The Rectangle Method". In short, we observe that all proofs of robustness in the above papers are done by constructing a "rectangle", while in the counterexample no such rectangle can be constructed. We then show that a rectangle can be constructed if and only if the tensor product is robust, and therefore the proof strategy of constructing a rectangle is complete.