TR98-060 Authors: Oded Goldreich, Ronitt Rubinfeld, Madhu Sudan

Publication: 8th October 1998 17:30

Downloads: 2901

Keywords:

This is a revised version of work which has appeared

in preliminary form in the 36th FOCS, 1995.

Given a function $f$ mapping $n$-variate inputs from a finite field

$F$ into $F$,

we consider the task of reconstructing a list of all $n$-variate

degree $d$ polynomials which agree with $f$

on a tiny but non-negligible fraction, $\d$, of the input space.

We give a randomized algorithm for solving this task which accesses

$f$ as a black box and

runs in time polynomial in ${\frac1\d},n$ and exponential in $d$,

provided $\d$ is $\Omega(\sqrt{d/|F|})$. For the special case

when $d= 1$, we solve this problem for all $\epsilon\eqdef\delta -

\frac1{|F|} >0$. In this case the running time of our algorithm is

bounded by a polynomial in $\frac1\e$ and $n$.

Our algorithm generalizes a previously known algorithm,

due to Goldreich and Levin, that solves this task for

the case when $F = \gf(2)$ (and $d=1$).

In the process we provide new bounds on the number of

degree $d$ polynomials that may agree with any given function

on $\d \geq \sqrt{d/|F|}$ fraction of the inputs. This result

is derived by generalizing a well-known bound from coding

theory on the number of codewords from an error-correcting code

that can be ``close'' to an arbitrary word --- our generalization

works for codes over arbitrary alphabets, while the previous result

held only for binary alphabets. This result may be of independent interest.