Abstract
A fundamental fact about polynomial interpolation is that k evaluations of a degree-(k-1) polynomial f are sufficient to determine f. This is also necessary in a strong sense: given k-1 evaluations, we learn nothing
about the value of f on any k'th point. Motivated by the *exact repair problem* for Reed-Solomon codes in distributed storage systems, we study a variant of the polynomial interpolation problem: instead of querying entire evaluations of f (which are elements of a large field F) to recover an unknown evaluation, we are allowed to query only a few bits of evaluations.
We show that in this model, one can do significantly better than in the traditional setting, in terms of the amount of information required to determine the missing evaluation. More precisely, only O(k) bits are necessary to recover the missing evaluation, and this result is optimal for linear methods.
Our result answers a question about the use of RS codes in distributed storage which was asked by Alex Dimakis during the Simons Institute's IT Program last year.
(Joint work with Venkat Guruswami)