ECCC-Report TR07-061https://eccc.weizmann.ac.il/report/2007/061Comments and Revisions published for TR07-061en-usThu, 16 Jun 2011 20:53:19 +0300
Revision 4
| On the Rectangle Method in proofs of Robustness of Tensor Products |
Or Meir
https://eccc.weizmann.ac.il/report/2007/061#revision4Given two codes $R$ and $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 on average from $R$ and $C$ respectively. Ben-Sasson and Sudan (ECCC TR04-046) have asked under which conditions the product $R \otimes C$ is robust. So far, a 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 is yet unknown.
In this work, we highlight a common theme in the previous works on the subject, which we call “the rectangle method”. In short, we observe that all proofs of robustness in the previous works are done by constructing a certain “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. Thu, 16 Jun 2011 20:53:19 +0300https://eccc.weizmann.ac.il/report/2007/061#revision4
Revision 3
| On the Rectangle Method in proofs of Robustness of Tensor Products |
Or Meir
https://eccc.weizmann.ac.il/report/2007/061#revision3Given two error correcting codes $R$,$C$, their tensor product $R\otimes C$ is the error correcting code that consists of all matrices whose rows are codewords of $R$ and whose columns are codewords of $C$. The code $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) asked under which conditions the product $R \otimes C$ is robust. So far, a 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 is yet unknown.
In this work, we highlight a common theme in the previous works on the subject, which we call “The Rectangle Method”. In short, we observe that all proofs of robustness in the previous works are done by constructing a certain “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. Mon, 13 Jun 2011 16:27:55 +0300https://eccc.weizmann.ac.il/report/2007/061#revision3
Revision 2
| On the Rectangle Method in proofs of Robustness of Tensor Products |
Or Meir
https://eccc.weizmann.ac.il/report/2007/061#revision2Given two error correcting codes $R$,$C$, their tensor product $R\otimes C$ is the error correcting code that consists of all matrices whose rows are codewords of $R$ and whose columns are codewords of $C$. The code $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) asked under which conditions the product $R \otimes C$ is robust. So far, a 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 is yet unknown.
In this work, we highlight a common theme in the previous works on the subject, which we call “The Rectangle Method”. In short, we observe that all proofs of robustness in the previous works are done by constructing a certain “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. Mon, 13 Jun 2011 16:26:56 +0300https://eccc.weizmann.ac.il/report/2007/061#revision2
Revision 1
| On the Rectangle Method in proofs of Robustness of Tensor Products |
Or Meir
https://eccc.weizmann.ac.il/report/2007/061#revision1Given 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.
Sun, 06 Apr 2008 00:00:00 +0300https://eccc.weizmann.ac.il/report/2007/061#revision1
Paper TR07-061
| On the Rectangle Method in proofs of Robustness of Tensor Products |
Or Meir
https://eccc.weizmann.ac.il/report/2007/061Given 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.
Thu, 12 Jul 2007 17:50:21 +0300https://eccc.weizmann.ac.il/report/2007/061