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

by Swastik Kopparty, Or Meir, Noga Ron-Zewi, and Shubhangi Saraf

#### Oded's comments

Indeed, the point is that,
*for codes of constant rate and constant relative distance*,
local testability, let alone local correctability,
was only known for a number of queries
that is polynomially related to the length of the code.
The current work obtains local testability and correctability
for codes of constant rate and constant relative distance
using query complexity that is subexponential in the logarithm
of the previously known query complexity.

**Note:**
This work grow out of a prior work by Or
(see choice Nr 154),
which in retrospect is defined (by the authors) as a
preliminary version of it.

**Update (July 2015):**
The local *testability* result (LTC),
but not the local correctability result (LCC),
has been improved by a recent work of the same authors
[ECCC TR15-110].
Specifically, the query complexity in the new work
is quasi-polylogarithmic.

#### The original 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(sqrt(logn)). Previously such codes were known to
exist only with n^e query complexity (for constant e>0), and there were
several, quite different, constructions known.

Our codes are based on a general distance-amplification method of Alon and
Luby (1996). 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 sub-constant
relative distance.

Along the way, we also construct LCCs and LTCs over large alphabets, with
the same query complexity exp(sqrt(logn)), 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(sqrt(logn)) 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.

See ECCC TR15-068.

Back to
list of Oded's choices.