**Recent Results in Local Codes**

[October, 2016] IAS/DIMACS postdoctoral fellow Noga Ron-Zewi
and her collaborators Swastik Kopparty
and Shubhangi
Saraf, both faculty members in Computer Science and
Mathematics at Rutgers, graduate students Sivakanth Gopi
and Rafael Oliveira
of Princeton University, and Or Meir of the
University of Haifa have made several recent breakthroughs in the
study of local codes.

In today’s world, huge amounts of data need to be reliably stored or
transmitted, but a certain amount of noise or corruption is
inevitable. An error-correcting code is a scheme for robustly
representing data in the form of codewords that allows one to detect
and correct errors in transmission. Locally testable and locally
decodable codes are special families of error-correcting codes that
admit highly efficient algorithms for error detection and
correction. In contrast to classical error-correcting codes that
must examine an entire transmission in order to detect or correct
errors, these codes enable detecting and correcting errors with high
probability in sublinear time by probing only a small number of
entries of a corrupted codeword.

Locally testable and locally decodable codes have been intensely
studied for the past two decades with numerous applications to
complexity theory, but their relevance to transmission and storage
of massive data and the use of local codes in cloud storage systems
has heightened recent interest.

Locally decodable codes provide a method to encode *k*-bit
messages into *n*-bit codewords such that even after a
constant fraction of the bits of the codeword get corrupted, any bit
of the original message can be recovered by looking at a small
number of bits of the corrupted codeword. Similarly, locally
testable codes provide a method to encode *k*-bit messages
into *n*-bit codewords such that there is an efficient tester
that can query an *n*-bit string in only a small number
of bits and decide whether the string is near or far from a true
codeword. The number of queries required by such algorithms is
called the query complexity and is a measure of running time. The
rate of the code is defined as the ratio between *k* and *n*
and measures the proportion of non-redundant information it
contains.

In a paper presented at the 2016 Annual Symposium on the Theory of
Computing (STOC 2016),
Kopparty, Meir, Ron-Zewi and Saraf substantially improved the query
complexity of such codes. Specifically, their work provides an
exponential improvement on the best-known query complexity of
locally testable and locally decodable codes. It describes new
families of locally testable codes of constant rate that can detect
a constant fraction of errors with query complexity
for a transmission of length *n*, and new families of locally
decodable codes of constant rate that can correct a constant
fraction of errors with query complexity
. Prior to their work, the best known query complexity for
such codes was of the form *n*^{c}* *for
a constant *c* > 0 that can be arbitrarily close to 0.

Ron-Zewi and her collaborators also showed that their codes can
achieve stronger trade-offs between rate and error correction
capability than were known previously. Over large alphabets (of
constant size), their codes approach the Singleton bound, meaning
that they achieve a tradeoff between rate and error correction
capability that is essentially best-possible for general
error-correcting codes. In follow-up work to be presented at the
28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Gopi,
Kopparty, Oliviera, Ron-Zewi, and Saraf showed that such codes can
also approach the Gilbert-Varshamov bound which is the best known
trade-off over the binary alphabet. This has the surprising
consequence that asking for a large-alphabet error-correcting code
to also be locally decodable or locally testable does not require
any sacrifice in terms of rate and error correction capability.

As an IAS/DIMACS postdoctoral fellow, Ron-Zewi spent the 2014-15
academic year at the Institute for
Advanced Study (IAS) and the 2015-16 academic year at DIMACS.
In a brief update for the IAS Newsletter, Avi Wigderson described
the results saying, “For both testing and decoding, new codes were
designed with rate approaching 1 (namely, negligible redundancy),
for which the number of queries needed is sub-polynomial! All
previous constructions with such query complexity have extremely
poor rate, whereas constant rate codes could only work with
polynomially many queries in the blocklength.”

In 2016, Ron-Zewi joined the faculty of the computer science
department at Ben-Gurion University in Israel following the
completion of her postdoc at DIMACS.

The results in their STOC 2016 paper were also presented by Saraf at
the DIMACS
Workshop on Cryptography and its Interactions: Learning Theory,
Coding Theory, and Data Structures in July and by Kopparty in
a TCS+ seminar in September. A video of Kopparty’s TCS+ talk is
available here.
A full version of this paper is available in two parts on the ECCC:
[TR15-068] [TR15-110]

The results that are to appear in their SODA 2017 paper were
presented by Kopparty at the Computational
Complexity workshop held at the Banff
International Research Station (BIRS) in September, 2016. A
video of Kopparty’s BIRS talk is here.
A full version of this paper is also available on the ECCC: [TR16-122].

Printable version of this story: [PDF]

**References:**

S. Kopparty, O. Meir, N. Ron-Zewi, and S. Saraf, “High rate
locally-correctable and locally-testable codes with sub-polynomial
query complexity,” Proceedings of the 48th Annual Symposium on
Theory of Computing (STOC), pages 25-32, 2016.

S. Gopi, S. Kopparty, R. Oliveira N. Ron-Zewi, and S. Saraf,
“Locally testable and locally correctable codes approaching the
Gilbert-Varshamov bound,” to appear in the Proceedings of the
ACM-SIAM Symposium on Discrete Algorithms, 2017.

DIMACS Homepage

Contacting the Center