Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR07-062 | 16th June 2011 20:55

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

RSS-Feed




Revision #2
Authors: Oded Goldreich, Or Meir
Accepted on: 16th June 2011 20:55
Downloads: 792
Keywords: 


Abstract:

Given 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.

Addressing this question, Paul Valiant (APPROX-RANDOM 2005) constructed 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 construction can be modified such that both codes have both constant rate and constant relative distance. We also provide an alternative proof for the non-robustness of the tensor product of those codes, based on the inverse direction of the “rectangle method” that was presented by the second author (ECCC TR07-061). We believe that this proof gives an additional intuition for why this construction works.


Revision #1 to TR07-062 | 13th June 2011 18:54

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





Revision #1
Authors: Oded Goldreich, Or Meir
Accepted on: 13th June 2011 18:54
Downloads: 871
Keywords: 


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) constructed 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 construction can be modified such that both codes have both constant rate and constant relative distance. We also provide an alternative proof for the non-robustness of the tensor product of the codes of Valiant, based on the inverse direction of the “rectangle method” that was presented by the second author (ECCC TR07-061). We believe that this proof gives an additional intuition for why this construction works.


Paper:

TR07-062 | 15th July 2007 00:00

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





TR07-062
Authors: Oded Goldreich, Or Meir
Publication: 15th July 2007 13:12
Downloads: 1221
Keywords: 


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.



ISSN 1433-8092 | Imprint