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.

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

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.

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

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.

The paper was modified.

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.