Robust Locally Testable Codes and Products of Codes
| dc.creator | Ben-Sasson, Eli | |
| dc.creator | Sudan, Madhu | |
| dc.date | 2004-08-30 | |
| dc.date.accessioned | 2026-07-07T08:17:42Z | |
| dc.date.available | 2026-07-07T08:17:42Z | |
| dc.description | We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of {\em robust} probabilistically checkable proofs, we introduce the notion of {\em robust} local testability of codes. We relate this notion to a product of codes introduced by Tanner, and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally, by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate, that are testable with poly-logarithmically many queries. We note these locally testable tensor codes can be obtained from {\em any} linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes. | |
| dc.identifier | https://arxiv.org/abs/cs/0408066 | |
| dc.identifier | http://arxiv.org/abs/cs/0408066 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134183 | |
| dc.subject | Information Theory | |
| dc.subject | Computational Complexity | |
| dc.subject | E.4 | |
| dc.title | Robust Locally Testable Codes and Products of Codes | |
| dc.type | text |