Open Problem Garden - The robustness of the tensor product - Comments

Results in (re: The robustness of the tensor product)

Anonymous — Wed, 17 Feb 2010 14:37:19 +0100

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 (re: The robustness of the tensor product)

ormeir — Mon, 16 Jul 2007 11:34:21 +0200

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

Given a matrix , let denote the distance from to the nearest codeword of . Let denote the average distance of a row of to , and let denote the average distance of a column of to . Finally, let denote the average of and .

The tensor product is said to be -robust iff for every matrix we have that .

The question is, under what conditions the tensor product is -robust for some constant .

To be more precise (re: The robustness of the tensor product)

ormeir — Mon, 16 Jul 2007 11:26:28 +0200

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.

To be more precise ... (re: The robustness of the tensor product)

Robert Samal — Sat, 14 Jul 2007 00:48:23 +0200

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

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

The robustness of the tensor product

ormeir — Fri, 13 Jul 2007 18:50:39 +0200

Author(s): Ben-Sasson; Sudan

Subject: Theoretical Comp. Sci. » Coding Theory

Problem Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).

The problem is to give a characterization of the pairs whose tensor product is robust.