The robustness of the tensor product

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]{}

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


% 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]{}).

[CR] D. Coppersmith and A. Rudra, On the robust testability of tensor products of codes, \href[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 \href[ECCC TR06-118]{}).

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

[M] Or Meir, On the Rectangle Method in proofs of Robustness of Tensor Products, \href[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.

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.