## Local Correctability of Expander Codes

by Brett Hemenway, Rafail Ostrovsky, and Mary Wootters

#### Oded's comments

As stated in the abstract (below),
the point is meeting the known result,
which was first obtained by a novel construction
(i.e., multiplicity codes),
by using known constructions.

#### The original abstract

In this work, we present the first local-decoding algorithm for
expander codes. This yields a new family of constant-rate codes that
can recover from a constant fraction of errors in the codeword symbols,
and where any symbol of the codeword can be recovered with high
probability by reading $N^\eps$ symbols from the corrupted codeword,
where $N$ is the block-length of the code.

Expander codes, introduced by Sipser and Spielman, are formed from
an expander graph $G = (V,E)$ of degree $d$, and an inner code of
block-length $d$ over an alphabet $\Sigma$. Each edge of the expander
graph is associated with a symbol in $\Sigma$. A string in $\Sigma^{E}$
will be a codeword if for each vertex in $V$, the symbols on the
adjacent edges form a codeword in the inner code.

We show that if the inner code has a smooth reconstruction
algorithm in the noiseless setting, then the corresponding expander
code has an efficient local-correction algorithm in the noisy setting.
Instantiating our construction with inner codes based on finite
geometries, we obtain novel locally decodable codes with rate
approaching one. This provides an alternative to the multiplicity codes
of Kopparty, Saraf and Yekhanin (STOC '11) and the lifted codes of Guo,
Kopparty and Sudan (ITCS '13).

Back to
list of Oded's choices.