Low-bandwidth Computation on Reed-Solomon-Encoded Data
Mary Wootters (Stanford University)

We study the problem of efficiently computing on encoded data. More specifically, we study the question of communication-efficient computation of a function $f(x)$, given access to an encoding $c = Enc(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 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 any linear function on Reed-Solomon-encoded data, even in the presence of erasures. This has applications in distributed storage, coded computation, and homomorphic secret sharing. This is joint work with Noah Shutty.