An error correcting code is said to be \emph{locally testable} if
there is a test that checks whether a given string is a codeword,
or rather far from the code, by reading only a small number of symbols
of the string. Locally testable codes (LTCs) are both interesting
in their own right, and have important applications in complexity
theory.

A long line of research tries to determine the best tradeoff between rate and distance that LTCs can achieve. In this work, we construct LTCs that have high rate (arbitrarily close to 1), have constant relative distance, and can be tested using $\left(\log n\right)^{O(\log\log n)}$ queries. This improves over the previous best construction of LTCs with high rate, by the same authors, which uses $\exp(\sqrt{\log n\cdot\log\log n})$ queries \cite{KMRS15}.

In fact, as in \cite{KMRS15}, our result is actually stronger: for binary codes, we obtain LTCs that match the Zyablov bound for any rate $0<r<1$. For codes over large alphabet (of constant size), we obtain
LTCs that approach the Singleton bound, for any rate $0<r<1$.

Grant of Or Meir was updated

An error correcting code is said to be \emph{locally testable} if
there is a test that checks whether a given string is a codeword,
or rather far from the code, by reading only a small number of symbols
of the string. Locally testable codes (LTCs) are both interesting
in their own right, and have important applications in complexity
theory.

A long line of research tries to determine the best tradeoff between rate and distance that LTCs can achieve. In this work, we construct LTCs that have high rate (arbitrarily close to 1), have constant relative distance, and can be tested using $\left(\log n\right)^{O(\log\log n)}$ queries. This improves over the previous best construction of LTCs with high rate, by the same authors, which uses $\exp(\sqrt{\log n\cdot\log\log n})$ queries \cite{KMRS15}.

In fact, as in \cite{KMRS15}, our result is actually stronger: for binary codes, we obtain LTCs that match the Zyablov bound for any rate $0<r<1$. For codes over large alphabet (of constant size), we obtain
LTCs that approach the Singleton bound, for any rate $0<r<1$.