Name
Abstract | ||
|---|---|---|
Given two binary linear codes R and C, their tensor product R 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 (6)): 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 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 smooth. We show that expander codes and locally-testable codes are smooth. This complements recent examples of P. Valiant (13) and Coppersmith and Rudra (9) of codes whose tensor product is not robustly testable. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1007/11830924_29 | Electronic Colloquium on Computational Complexity (ECCC) |
Keywords | Field | DocType |
following test,locally-testable code,p. valiant,tensor product r,expander code,ldpc code,robust local testability,tensor product,random row,binary linear codes r,recent example,matrix m | Tensor product,Discrete mathematics,Combinatorics,Matrix (mathematics),Low-density parity-check code,Block code,Binary code,Expander code,Error detection and correction,Linear code,Mathematics | Journal |
Volume | Issue | ISSN |
13 | 118 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-38044-2 | 21 | 0.81 |
References | Authors | |
13 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Irit Dinur | 1 | 1187 | 85.67 |
| Madhu Sudan | 2 | 5616 | 591.68 |
| Avi Wigderson | 3 | 8205 | 1064.31 |