Revision #1 Authors: Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

Accepted on: 25th February 2016 03:15

Downloads: 934

Keywords:

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

TR15-110 Authors: Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf

Publication: 8th July 2015 04:05

Downloads: 1320

Keywords:

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