ECCC-Report TR10-004https://eccc.weizmann.ac.il/report/2010/004Comments and Revisions published for TR10-004en-usFri, 07 May 2010 17:06:06 +0300
Revision 3
| Low Rate Is Insufficient for Local Testability |
Eli Ben-Sasson,
Michael Viderman
https://eccc.weizmann.ac.il/report/2010/004#revision3Locally testable codes are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.
A linear code $C \subseteq \F_2^n$ is called sparse if $\dim(C) = O(\log(n))$.
We say that a code $C\subseteq \F_2^n$ is $\epsilon$-biased if all nonzero codewords of $C$ have relative weight in the range $(\frac{1}{2} - \epsilon,\frac{1}{2}+ \epsilon)$, where $\epsilon$ may be a function of $n$.
Kaufman and Sudan \cite{KS07} proved that all sparse linear codes with relative distance $\frac{1}{2}-n^{-\Omega(1)}$ are locally testable. Moreover, they showed that all sparse $n^{-\Omega(1)}$-biased linear codes are locally decodable. In particular sparse random codes are locally testable and are locally decodable with probability $1-o(1)$.
Kopparty and Saraf \cite{KopS09} conjectured that all sparse linear codes (even with a bad distance) are locally testable.
In this paper we refute this conjecture by showing that for every $d(n)$ ranging from $\omega(1)$ to $\Omega(n)$ there exists a family of codes $\set{C^{(n)} \subset \F_2^n}_{n\in \ints}$ with linear distance and $\dim(C^{(n)})= \Theta(d(n))$ which are not locally testable (decodable). Furthermore, we show that there exists a family of codes $\set{C^{(n)} \subset \F_2^n}_{n\in \ints}$ with bias $n^{-o(1)}$ and $\dim(C^{(n)})= \log(n)$ which are not locally testable (decodable). This also shows that the results of Kaufman and Sudan \cite{KS07} were surprisingly tight.Fri, 07 May 2010 17:06:06 +0300https://eccc.weizmann.ac.il/report/2010/004#revision3
Revision 2
| Low Rate Is Insufficient for Local Testability |
Eli Ben-Sasson,
Michael Viderman
https://eccc.weizmann.ac.il/report/2010/004#revision2Locally testable codes are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.
A linear code $C \subseteq \F_2^n$ is called sparse if $\dim(C) = O(\log(n))$.
We say that a code $C\subseteq \F_2^n$ is $\epsilon$-biased if all nonzero codewords of $C$ have relative weight in the range $(\frac{1}{2} - \epsilon,\frac{1}{2}+ \epsilon)$, where $\epsilon$ may be a function of $n$.
Kaufman and Sudan \cite{KS07} proved that for sparse linear codes with relative distance $\frac{1}{2}-n^{-\Omega(1)}$ are locally testable. Moreover, they showed that all sparse $n^{-\Omega(1)}$-biased linear codes are locally decodable. In particular sparse random codes are locally testable and are locally decodable with probability $1-o(1)$.
Kopparty and Saraf \cite{KopS09} conjectured that all sparse linear codes (even with a bad distance) are locally testable.
In this paper we refute this conjecture by showing that for every $d(n)$ ranging from $\omega(1)$ to $\Omega(n)$ there exists a family of codes $\set{C^{(n)} \subset \F_2^n}_{n\in \ints}$ with linear distance and $\dim(C^{(n)})= \Theta(d(n))$ which are not locally testable (decodable).
Furthermore, we show that there exists a family of codes $\set{C^{(n)} \subset \F_2^n}_{n\in \ints}$ with bias $n^{-o(1)}$ and $\dim(C^{(n)})= \log(n)$ which are not locally testable (decodable).
This also shows that the results of Kaufman and Sudan \cite{KS07} were surprisingly tight.Tue, 16 Feb 2010 11:52:09 +0200https://eccc.weizmann.ac.il/report/2010/004#revision2
Revision 1
| Low Rate Is Insufficient for Local Testability |
Eli Ben-Sasson,
Michael Viderman
https://eccc.weizmann.ac.il/report/2010/004#revision1Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.
Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable and decodable, in particular sparse random codes are locally testable and decodable.
Kopparty and Saraf \cite{KS09} conjectured that all sparse linear codes, i.e., codes with logarithmic dimension, are locally testable.
In this paper we refute this conjecture by showing that for every $\epsilon > 0$ there exists a family of codes $\set{C_{\epsilon}^{(n)} \subset \F_2^n}_{n\in \ints}$ with relative distance $(1/2-\epsilon)$ and $\dim(C_{\epsilon}^{(n)})= \Theta(\log(n))$ which are not locally testable and not locally decodable.
% Michael: I changed the next sentence.
Moreover, for every $d(n)$ ranging from $\omega(1)$ to $\Omega(n)$ we show a family of codes $\set{C_{\epsilon}^{(n)} \subset \F_2^n}_{n\in \ints}$ with relative distance $(1/2-\epsilon)$ and $\dim(C_{\epsilon}^{(n)})= \Theta(d(n))$ which are not locally testable (decodable).
This also shows that the requirement of ``low-bias'' in the work of Kaufman and Sudan \cite{KS07} is necessary.Thu, 28 Jan 2010 23:15:47 +0200https://eccc.weizmann.ac.il/report/2010/004#revision1
Paper TR10-004
| Low Rate Is Insufficient for Local Testability |
Eli Ben-Sasson,
Michael Viderman
https://eccc.weizmann.ac.il/report/2010/004Locally testable codes (LTCs) are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.
Kaufman and Sudan \cite{KS07} proved that sparse, low-bias linear codes are locally testable (in particular sparse random codes are locally testable).
Kopparty and Saraf \cite{KopS09} conjectured that all linear sparse codes (codes with logarithmic dimension) are locally testable.
In this paper we refute this conjecture by showing that for every $\epsilon > 0$ there exists a code $C_{\epsilon} \subset \F_2^n$ with relative distance $(1/2-\epsilon)$ and $\dim(C)= \Theta(\log(n))$ which is not locally testable and not locally decodable. Moreover, our construction can achieve any (non-constant) dimension, e.g. we can construct $C$ s.t. $\dim(C) = \log \log (n)$ and $C$ is not locally testable (decodable). This also shows that the requirement of ``low-bias'' in the work of Kaufman and Sudan \cite{KS07} was necessarily.Wed, 06 Jan 2010 10:01:44 +0200https://eccc.weizmann.ac.il/report/2010/004