loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2009 24th Annual IEEE Conference on Computational Complexity
Locally Testable Codes Require Redundant Testers
Paris, France
July 15-July 18
ISBN: 978-0-7695-3717-7
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) {\em 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 {\em 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 {\em 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.
Index Terms:
linear codes, property testing, dual codes, LDPC codes, lower bounds
Citation:
Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman, "Locally Testable Codes Require Redundant Testers," ccc, pp.52-61, 2009 24th Annual IEEE Conference on Computational Complexity, 2009
Usage of this product signifies your acceptance of the Terms of Use.