ECCC-Report TR15-110https://eccc.weizmann.ac.il/report/2015/110Comments and Revisions published for TR15-110en-usThu, 25 Feb 2016 03:15:32 +0200
Revision 1
| High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity |
Noga Ron-Zewi,
Swastik Kopparty,
Shubhangi Saraf,
Or Meir
https://eccc.weizmann.ac.il/report/2015/110#revision1An 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$.Thu, 25 Feb 2016 03:15:32 +0200https://eccc.weizmann.ac.il/report/2015/110#revision1
Paper TR15-110
| High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity |
Noga Ron-Zewi,
Swastik Kopparty,
Shubhangi Saraf,
Or Meir
https://eccc.weizmann.ac.il/report/2015/110An 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$.Wed, 08 Jul 2015 04:05:32 +0300https://eccc.weizmann.ac.il/report/2015/110