# 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

\begin{problem} Given two codes $R,C$, their \textbf{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 \textbf{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. \end{problem}

% You may use many features of TeX, such as % arbitrary math (between $...$ and $$...$$) % \begin{theorem}...\end{theorem} environment, also works for question, problem, conjecture, ... % % Our special features: % Links to wikipedia: \Def {mathematics} or \Def[coloring]{Graph_coloring} % General web links: \href [The On-Line Encyclopedia of Integer Sequences]{http://www.research.att.com/~njas/sequences/}

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

## Bibliography

% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

*[BS] Eli Ben-Sasson, Madhu Sudan, Robust locally testable codes and products of codes, APPROX-RANDOM 2004, pp. 286-297 (See \href[ECCC TR04-046]{http://eccc.hpi-web.de/eccc-reports/2004/TR04-046/index.html}).

[CR] D. Coppersmith and A. Rudra, On the robust testability of tensor products of codes, \href[ECCC TR07-061]{http://eccc.hpi-web.de/eccc-reports/2005/TR05-104/index.html}.

[DSW] Irit Dinur, Madhu Sudan and Avi Wigderson, Robust local testability of tensor products of LDPC codes, APPROX-RANDOM 2006, pp. 304-315 (See \href[ECCC TR06-118]{http://eccc.hpi-web.de/eccc-reports/2006/TR06-118/index.html}).

[GM] Oded Goldreich, Or Meir, The Tensor Product of Two Good Codes Is Not Necessarily Robustly Testable, \href[ECCC TR07-062]{http://eccc.hpi-web.de/eccc-reports/2007/TR07-062/index.html}.

[M] Or Meir, On the Rectangle Method in proofs of Robustness of Tensor Products, \href[ECCC TR07-061]{http://eccc.hpi-web.de/eccc-reports/2007/TR07-061/index.html}.

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

### Results in

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

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)$.

The question is, under what conditions the tensor product $R \otimes C$ is $\alpha$-robust for some constant $\alpha$.

### To be more precise ...

1) When you say codes, do you mean linear codes?

2) What distance you are using when you're saying "far from"?

### To be more precise

1) The question is most interesting for linear codes, but it can also be defined for non-linear codes.

2) The distance is (relative or absolute) Hamming Distance.

## Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.