ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR15-068 | 9th November 2015 03:06

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity

RSS-Feed




Revision #2
Authors: Swastik Kopparty, Or Meir, Noga Ron-Zewi, Shubhangi Saraf
Accepted on: 9th November 2015 03:06
Downloads: 192
Keywords: 


Abstract:

In this work, we construct the first locally-correctable codes (LCCs),
and locally-testable codes (LTCs) with constant rate, constant relative
distance, and sub-polynomial query complexity. Specifically, we show
that there exist binary LCCs and LTCs with block length $n$, constant
rate (which can even be taken arbitrarily close to 1), constant relative
distance, and query complexity $\exp(\tilde{O}(\sqrt{\log n}))$.
Previously such codes were known to exist only with $\Omega(n^{\beta})$
query complexity (for constant $\beta>0$), and there were several,
quite different, constructions known.

In addition to having small query complexity, our codes also achieve
better trade-offs between the rate and the relative distance than were previously known to be achievable by LCCs or LTCs.
Specifically,
over large (but constant size) alphabet, our codes approach the Singleton
bound, that is, they have almost the best-possible relationship between
their rate and distance. This has the surprising consequence that
asking for a large-alphabet error-correcting code to further be an
LCC or LTC with sub-polynomial query complexity does not require any
sacrifice in terms of rate and distance! Over the binary alphabet, our codes meet the Zyablov bound.
Such trade-offs between the rate and the relative distance were previously
not known for any $o(n)$ query complexity. Our results on LCCs also
immediately give locally-decodable codes (LDCs) with the same parameters.

Our codes are based on a technique of Alon, Edmonds and Luby~\cite{AEL95,AL96_codes}.
We observe that this technique can be used as a general distance-amplification
method, and show that it interacts well with local correctors and
testers. We obtain our main results by applying this method to suitably
constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant
relative distance}.



Changes to previous version:

Singleton bound is obtained over constant size alphabet, added proof that codes obtain the Zyablov bound, and other small changes


Revision #1 to TR15-068 | 21st April 2015 20:02

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity


Abstract:

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity $\exp(\tilde{O}(\sqrt{\log n}))$. Previously such codes were known to exist only with $\Omega(n^{\beta})$ query complexity (for constant $\beta > 0$), and there were several, quite different, constructions known.

Our codes are based on a general distance-amplification method of Alon and Luby~\cite{AL96_codes}. We show that this method interacts well with local correctors and testers, and obtain our main results by applying it to suitably constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant relative distance}.

Along the way, we also construct LCCs and LTCs over large alphabets, with the same query complexity $\exp(\tilde{O}(\sqrt{\log n}))$, which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC with $\exp(\tilde{O}(\sqrt{\log n}))$ query complexity does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any $o(n)$ query complexity.

Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters.



Changes to previous version:

Or Meir is also a co-author, his name was undeliberately omitted from previous version due to technical error.


Paper:

TR15-068 | 21st April 2015 17:13

High rate locally-correctable and locally-testable codes with sub-polynomial query complexity


Abstract:

In this work, we construct the first locally-correctable codes (LCCs), and locally-testable codes (LTCs) with constant rate, constant relative distance, and sub-polynomial query complexity. Specifically, we show that there exist binary LCCs and LTCs with block length $n$, constant rate (which can even be taken arbitrarily close to 1), constant relative distance, and query complexity $\exp(\tilde{O}(\sqrt{\log n}))$. Previously such codes were known to exist only with $\Omega(n^{\beta})$ query complexity (for constant $\beta > 0$), and there were several, quite different, constructions known.

Our codes are based on a general distance-amplification method of Alon and Luby~\cite{AL96_codes}. We show that this method interacts well with local correctors and testers, and obtain our main results by applying it to suitably constructed LCCs and LTCs in the non-standard regime of \emph{sub-constant relative distance}.

Along the way, we also construct LCCs and LTCs over large alphabets, with the same query complexity $\exp(\tilde{O}(\sqrt{\log n}))$, which additionally have the property of approaching the Singleton bound: they have almost the best-possible relationship between their rate and distance. This has the surprising consequence that asking for a large alphabet error-correcting code to further be an LCC or LTC with $\exp(\tilde{O}(\sqrt{\log n}))$ query complexity does not require any sacrifice in terms of rate and distance! Such a result was previously not known for any $o(n)$ query complexity.

Our results on LCCs also immediately give locally-decodable codes (LDCs) with the same parameters.



ISSN 1433-8092 | Imprint