ECCC-Report TR09-126https://eccc.weizmann.ac.il/report/2009/126Comments and Revisions published for TR09-126en-usWed, 20 Jan 2010 10:01:57 +0200
Revision 3
| Locally Testable Codes Require Redundant Testers |
Eli Ben-Sasson,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan,
Michael Viderman
https://eccc.weizmann.ac.il/report/2009/126#revision3 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.
Our main theorem is a special case of a more general theorem that applies to any tester for an arbitrary linear locally testable code $\C$. The general theorem can be used, for instance, to provide an arguably simpler proof of the main result of \cite{3CNF} which says that testing random low density parity check (LDPC) codes requires linear query complexity. Informally, our more general theorem says the following. Take any basis $B$ for the dual code of $\C$ that is comprised of words of small support, i.e., every element of $B$ has very few nonzero entries. Then the dual code of $\C$ must contain many words that are \itone not in $B$, \ittwo have small support, and most importantly, \itthree are a linear combination of a constant fraction of $B$.Wed, 20 Jan 2010 10:01:57 +0200https://eccc.weizmann.ac.il/report/2009/126#revision3
Revision 2
| Locally Testable Codes Require Redundant Testers |
Eli Ben-Sasson,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan,
Michael Viderman
https://eccc.weizmann.ac.il/report/2009/126#revision2 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.
Our main theorem is a special case of a more general theorem that applies to any tester for an arbitrary linear locally testable code $\C$. The general theorem can be used, for instance, to provide an arguably simpler proof of the main result of \cite{3CNF} which says that testing random low density parity check (LDPC) codes requires linear query complexity. Informally, our more general theorem says the following. Take any basis $B$ for the dual code of $C$ that is comprised of words of small support, i.e., every element of $B$ has very few nonzero entries. Then the dual code of $C$ must contain many words that are \itone not in $B$, \ittwo have small support, and most importantly, \itthree are a linear combination of a constant fraction of $B$.Fri, 11 Dec 2009 14:53:25 +0200https://eccc.weizmann.ac.il/report/2009/126#revision2
Revision 1
| Locally Testable Codes Require Redundant Testers |
Eli Ben-Sasson,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan,
Michael Viderman
https://eccc.weizmann.ac.il/report/2009/126#revision1Locally 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.
Fri, 27 Nov 2009 10:56:29 +0200https://eccc.weizmann.ac.il/report/2009/126#revision1
Paper TR09-126
| Locally Testable Codes Require Redundant Testers |
Michael Viderman,
Eli Ben-Sasson,
Venkatesan Guruswami,
Tali Kaufman,
Madhu Sudan
https://eccc.weizmann.ac.il/report/2009/126Locally 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.
Fri, 27 Nov 2009 08:31:02 +0200https://eccc.weizmann.ac.il/report/2009/126