ECCC-Report TR06-118https://eccc.weizmann.ac.il/report/2006/118Comments and Revisions published for TR06-118en-usSun, 10 Sep 2006 20:32:33 +0300
Paper TR06-118
| Robust Local Testability of Tensor Products of LDPC Codes |
Irit Dinur,
Madhu Sudan,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2006/118Given 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.
Sun, 10 Sep 2006 20:32:33 +0300https://eccc.weizmann.ac.il/report/2006/118