A fundamental fact about polynomial interpolation is that k evaluations of a degree-(k-1) polynomial f(x) are sufficient to determine f(x). This is also necessary in a strong sense: given k-1 evaluations of f, we learn nothing about f(a) for any k'th point a. We study a variant of this polynomial interpolation problem. Instead of getting complete evaluations of f(x) -- which may live in a large finite field F -- we are allowed to ask for *partial* evaluations -- that is, a few symbols from a subfield of F, rather than one symbol from F itself -- from the evaluations f(x). The goal is again to determine f(a) for some point a that was not queried, while minimizing the total amount of information gathered from the evaluations.
We show that in this model, one can do significantly better than the traditional setting, in terms of the amount of information required to determine f(a). Our motivation comes from distributed storage systems, and from the exact repair problem for Reed-Solomon codes. The traditional use of Reed-Solomon codes for distributed storage is analogous to the standard interpolation problem: each node in a system stores an evaluation f(a), and if one node fails we can recover it by reading k other nodes. However, each node is perfectly free to send less information, leading to the modified interpolation problem above. The quickly-developing field of regenerating codes has yielded several codes which take advantage of this freedom. However, these regenerating codes are not Reed-Solomon codes, and RS codes are still often used in practice. Our results imply that, in fact, one can use Reed-Solomon codes to also take advantage of this freedom to download partial symbols. In some (disclaimer: less standard) parameter regimes, our scheme for Reed-Solomon codes outperforms all known regenerating codes.
This is joint work with Venkat Guruswami.