  We study the problem of efficiently computing on encoded data. More
specifically, we study the question of low-bandwidth computation of functions
$F:\mathbb{F}^k \to \mathbb{F}$ of some data $x \in \mathbb{F}^k$, given access
to an encoding $c \in \mathbb{F}^n$ of $x$ under an error correcting code. In
our model -- relevant in distributed storage, distributed computation and
secret sharing -- each symbol of $c$ is held by a different party, and we aim
to minimize the total amount of information downloaded from each party in order
to compute $F(x)$. Special cases of this problem have arisen in several
domains, and we believe that it is fruitful to study this problem in
generality.
  Our main result is a low-bandwidth scheme to compute linear functions for
Reed-Solomon codes, even in the presence of erasures. More precisely, let
$\epsilon > 0$ and let $\mathcal{C}: \mathbb{F}^k \to \mathbb{F}^n$ be a
full-length Reed-Solomon code of rate $1 - \epsilon$ over a field $\mathbb{F}$
with constant characteristic. For any $\gamma \in [0, \epsilon)$, our scheme
can compute any linear function $F(x)$ given access to any $(1 -
\gamma)$-fraction of the symbols of $\mathcal{C}(x)$, with download bandwidth
$O(n/(\epsilon - \gamma))$ bits. In contrast, the naive scheme that involves
reconstructing the data $x$ and then computing $F(x)$ uses $\Theta(n \log n)$
bits. Our scheme has applications in distributed storage, coded computation,
and homomorphic secret sharing.
