Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ROBUST:
Reports tagged with robust:
TR06-118 | 2nd September 2006
Irit Dinur, Madhu Sudan, Avi Wigderson

#### Robust Local Testability of Tensor Products of LDPC Codes

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

TR07-061 | 12th July 2007
Or Meir

#### On the Rectangle Method in proofs of Robustness of Tensor Products

Revisions: 4

Given linear 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$
more >>>

TR07-062 | 15th July 2007
Oded Goldreich, Or Meir

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

Revisions: 2

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

TR09-007 | 9th January 2009
Eli Ben-Sasson, Michael Viderman

#### Tensor Products of Weakly Smooth Codes are Robust

We continue the study of {\em robust} tensor codes and expand the
class of base codes that can be used as a starting point for the
construction of locally testable codes via robust two-wise tensor
products. In particular, we show that all unique-neighbor expander
codes and all locally correctable codes, ... more >>>

ISSN 1433-8092 | Imprint