Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #3 to TR10-004 | 7th May 2010 17:06

Low Rate Is Insufficient for Local Testability

RSS-Feed

Abstract:

Locally 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.



Changes to previous version:

The tight upper bound on the redundancy of the tester for LTC was added.


Revision #2 to TR10-004 | 16th February 2010 11:52

Low Rate Is Insufficient for Local Testability





Revision #2
Authors: Eli Ben-Sasson, Michael Viderman
Accepted on: 16th February 2010 11:52
Downloads: 1203
Keywords: 


Abstract:

Locally 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.



Changes to previous version:

The tightness of the "low-bias" requirement in the work of Kaufman and Sudan was proved.


Revision #1 to TR10-004 | 28th January 2010 23:15

Low Rate Is Insufficient for Local Testability





Revision #1
Authors: Eli Ben-Sasson, Michael Viderman
Accepted on: 28th January 2010 23:15
Downloads: 1325
Keywords: 


Abstract:

Locally 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.



Changes to previous version:

The paper was modified.


Paper:

TR10-004 | 6th January 2010 09:59

Low Rate Is Insufficient for Local Testability





TR10-004
Authors: Eli Ben-Sasson, Michael Viderman
Publication: 6th January 2010 10:01
Downloads: 1251
Keywords: 


Abstract:

Locally 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.



ISSN 1433-8092 | Imprint