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 #1 to TR15-110 | 25th February 2016 03:15

High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity

RSS-Feed




Revision #1
Authors: Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
Accepted on: 25th February 2016 03:15
Downloads: 896
Keywords: 


Abstract:

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



Changes to previous version:

Grant of Or Meir was updated


Paper:

TR15-110 | 8th July 2015 01:46

High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity


Abstract:

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



ISSN 1433-8092 | Imprint