Locally-correctable codes (LCCs) and locally-testable
codes (LTCs) are error-correcting codes that admit \emph{local} algorithms
for correction and detection of errors. Those algorithms are local
in the sense that they only query a small number of entries of the
corrupted codeword. The fundamental question about LCCs and LTCs is
to determine the optimal tradeoff between their rate, distance and
query complexity.
In this work, we construct the first LCCs and LTCs with constant rate,
constant relative distance, and sub-polynomial query complexity. Specifically,
we show that there exist LCCs and LTCs with block length $n$, constant
rate (which can even be taken arbitrarily close to 1) and constant
relative distance, whose query complexity is $\exp(\tilde{O}(\sqrt{\log n}))$
(for LCCs) and $\left(\log n\right)^{O(\log\log n)}$ (for LTCs).
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. 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.
Previous version was merged with:
High-rate Locally-testable Codes with Quasi-polylogarithmic Query Complexity, https://eccc.weizmann.ac.il/report/2015/110/
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
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.
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.
