Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-118 | 2nd September 2006 00:00

Robust Local Testability of Tensor Products of LDPC Codes


Authors: Irit Dinur, Madhu Sudan, Avi Wigderson
Publication: 10th September 2006 20:32
Downloads: 3276


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 if the received word is in R (or C).
Robustness of the test implies that if a matrix M is far from R\otimes C, then a significant fraction of the rows (or columns) of M are far from codewords of R (or C).

We show that this test *is* robust, provided one of the codes is
what we refer to as {\em smooth}. We show that expander codes and
locally-testable codes are smooth. This complements recent examples
of P. Valiant~\cite{Valiant05} and Coppersmith and Rudra~\cite{CoppersmithR05} of codes whose tensor product is not
robustly testable.

ISSN 1433-8092 | Imprint