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

Accepted on: 9th November 2015 03:06

Downloads: 353

Keywords:

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

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

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

Accepted on: 21st April 2015 20:02

Downloads: 419

Keywords:

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.

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

TR15-068 Authors: Swastik Kopparty, Noga Ron-Zewi, Shubhangi Saraf

Publication: 21st April 2015 19:34

Downloads: 621

Keywords:

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.