Theory of Computing
-------------------
Title     : Query Complexity Lower Bounds for Reconstruction of Codes
Authors   : Sourav Chakraborty, Eldar Fischer, and Arie Matsliah
Volume    : 10
Number    : 19
Pages     : 515-533
URL       : https://theoryofcomputing.org/articles/v010a019

Abstract
--------

We investigate the problem of _local reconstruction_, as defined by
Saks and Seshadhri (2008), in the context of error correcting codes.

The first problem we address is that of _message reconstruction_,
where given oracle access to a corrupted encoding $w \in \{0,1\}^n$ of
some message $x \in \{0,1\}^k$ our goal is to probabilistically
recover $x$ (or some portion of it). This should be done by a
procedure (reconstructor) that given an index $i$ as input, probes $w$
at few locations and outputs the value of $x_i$. The reconstructor can
(and indeed must) be randomized, with all its randomness specified in
advance by a single random seed, and the main requirement is that for
_most_ random seeds, _all_ values $x_1,\ldots,x_k$ are reconstructed
correctly. (Notice that swapping the order of "for most random seeds"
and "for all $x_1,\ldots,x_k$" would make the definition equivalent to
standard _Local Decoding_.)

A message reconstructor can serve as a "filter" that allows evaluating
certain classes of algorithms on $x$ safely and efficiently. For
instance, to run a parallel algorithm, one can initialize several
copies of the reconstructor with the same random seed, and then they
can autonomously handle decoding requests while producing outputs that
are consistent with the original message $x$. Another motivation for
studying message reconstruction arises from the theory of Locally
Decodable Codes.

The second problem that we address is _codeword reconstruction_, which
is similarly defined, but instead of reconstructing the message the
goal is to reconstruct the codeword itself, given an oracle access to
its corrupted version.

Error correcting codes that admit message and codeword reconstruction
can be obtained from Locally Decodable Codes (LDC) and Self
Correctable Codes (SCC) respectively. The main contribution of this
paper is a proof that in terms of query complexity, these
constructions are close to best possible in many settings, even when
we disregard the length of the encoding.

A conference version of this paper appeared in the Proceedings of the
Second Symposium on Innovations in Computer Science (ICS 2011).