Locally Testable Codes Require Redundant Testers
Locally testable codes (LTCs) are error- correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) many...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Online Access: | http://hdl.handle.net/1721.1/52520 |
| _version_ | 1826189454724825088 |
|---|---|
| author | Viderman, Michael Guruswami, Venkatesan Ben-Sasson, Eli Kaufman-Halman, Tali Sudan, Madhu |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Viderman, Michael Guruswami, Venkatesan Ben-Sasson, Eli Kaufman-Halman, Tali Sudan, Madhu |
| author_sort | Viderman, Michael |
| collection | MIT |
| description | Locally testable codes (LTCs) are error- correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) many small weight codewords. Examining this feature appears to be one of the promising approaches to proving limitation results for (i.e., upper bounds on the rate of) LTCs. Unfortunately till now it was not even known if LTCs need to be non-trivially redundant, i.e., need to have one linear dependency among the low-weight codewords in its dual. In this paper we give the first lower bound of this form, by showing that every positive rate constant query strong LTC must have linearly many redundant low-weight codewords in its dual. We actually prove the stronger claim that the actual test itself must use a linear number of redundant dual codewords (beyond the minimum number of basis elements required to characterize the code); in other words, non-redundant (in fact, low redundancy) local testing is impossible. |
| first_indexed | 2024-09-23T08:14:55Z |
| format | Article |
| id | mit-1721.1/52520 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:14:55Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/525202022-09-23T11:53:59Z Locally Testable Codes Require Redundant Testers Viderman, Michael Guruswami, Venkatesan Ben-Sasson, Eli Kaufman-Halman, Tali Sudan, Madhu Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Sudan, Madhu Kaufman-Halman, Tali Sudan, Madhu Locally testable codes (LTCs) are error- correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes whose duals have (superlinearly) many small weight codewords. Examining this feature appears to be one of the promising approaches to proving limitation results for (i.e., upper bounds on the rate of) LTCs. Unfortunately till now it was not even known if LTCs need to be non-trivially redundant, i.e., need to have one linear dependency among the low-weight codewords in its dual. In this paper we give the first lower bound of this form, by showing that every positive rate constant query strong LTC must have linearly many redundant low-weight codewords in its dual. We actually prove the stronger claim that the actual test itself must use a linear number of redundant dual codewords (beyond the minimum number of basis elements required to characterize the code); in other words, non-redundant (in fact, low redundancy) local testing is impossible. 2010-03-11T19:42:22Z 2010-03-11T19:42:22Z 2009-09 Article http://purl.org/eprint/type/ConferencePaper 978-0-7695-3717-7 1093-0159 http://hdl.handle.net/1721.1/52520 Ben-Sasson, E. et al. “Locally Testable Codes Require Redundant Testers.” Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on. 2009. 52-61. © 2009 IEEE en_US http://dx.doi.org/10.1109/CCC.2009.6 2009 Computational Complexity Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Institute of Electrical and Electronics Engineers Joanne Hanley |
| spellingShingle | Viderman, Michael Guruswami, Venkatesan Ben-Sasson, Eli Kaufman-Halman, Tali Sudan, Madhu Locally Testable Codes Require Redundant Testers |
| title | Locally Testable Codes Require Redundant Testers |
| title_full | Locally Testable Codes Require Redundant Testers |
| title_fullStr | Locally Testable Codes Require Redundant Testers |
| title_full_unstemmed | Locally Testable Codes Require Redundant Testers |
| title_short | Locally Testable Codes Require Redundant Testers |
| title_sort | locally testable codes require redundant testers |
| url | http://hdl.handle.net/1721.1/52520 |
| work_keys_str_mv | AT vidermanmichael locallytestablecodesrequireredundanttesters AT guruswamivenkatesan locallytestablecodesrequireredundanttesters AT bensassoneli locallytestablecodesrequireredundanttesters AT kaufmanhalmantali locallytestablecodesrequireredundanttesters AT sudanmadhu locallytestablecodesrequireredundanttesters |