The robustness of the tensor product

Importance: High ✭✭✭

Author(s):	Ben-Sasson, Eli
	Sudan, Madhu

Subject:	Theoretical Computer Science
	» Coding Theory

Keywords:	codes
	coding
	locally testable
	robustness

Recomm. for undergrads: no

Posted	by:	ormeir
	on:	July 13th, 2007

Problem Given two codes $R,C$ , their Tensor Product $R \otimes C$ is the code that consists of the 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 whenever a matrix $M$ is far from $R \otimes C$ , the rows (columns) of $M$ are far from $R$ ( $C$ , respectively).

The problem is to give a characterization of the pairs $R,C$ whose tensor product is robust.

The question is studied in the context of Locally Testable Codes.

Bibliography

*[BS] Eli Ben-Sasson, Madhu Sudan, Robust locally testable codes and products of codes, APPROX-RANDOM 2004, pp. 286-297 (See ECCC TR04-046).

[CR] D. Coppersmith and A. Rudra, On the robust testability of tensor products of codes, ECCC TR07-061.

[DSW] Irit Dinur, Madhu Sudan and Avi Wigderson, Robust local testability of tensor products of LDPC codes, APPROX-RANDOM 2006, pp. 304-315 (See ECCC TR06-118).

[GM] Oded Goldreich, Or Meir, The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable, ECCC TR07-062.

[M] Or Meir, On the Rectangle Method in proofs of Robustness of Tensor Products, ECCC TR07-061.

[V] Paul Valiant, The Tensor Product of Two Codes Is Not Necessarily Robustly Testable, APPROX-RANDOM 2005, pp. 472-481.

* indicates original appearance(s) of problem.

add new comment

Results in

On February 17th, 2010 Anonymous says:

Eli Ben-Sasson and Michael Viderman. "Composition of semi-LTCs by two-wise Tensor Products" (RANDOM 09)

Eli Ben-Sasson and Michael Viderman. "Tensor Products of Weakly Smooth Codes are Robust" (RANDOM 08)

The formal definition of robustness, and of the problem

On July 16th, 2007 ormeir says:

In all of the following definitions, the term "distance" refers to "relative Hamming distance".

Given a matrix $M$ , let $\delta_{R \otimes C}(M)$ denote the distance from $M$ to the nearest codeword of $R \otimes C$ . Let $\delta_{\rm{row}}(M)$ denote the average distance of a row of $M$ to $R$ , and let $\delta_{\rm{col}}(M)$ denote the average distance of a column of $M$ to $C$ . Finally, let $\rho(M)$ denote the average of $\delta_{\rm{row}}(M)$ and $\delta_{\rm{col}}(M)$ .

The tensor product $R \otimes C$ is said to be $\alpha$ -robust iff for every matrix $M$ we have that $\rho(M) \ge \alpha \cdot \delta_{R \otimes C}(M)$ .