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.