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$
more >>>

We present an optimal ``worst-case exact to average-case approximate'' reduction for matrix multiplication over a finite field of prime order $p$. Any efficient algorithm that correctly computes, in expectation, at least $(\frac{1}{p} + \varepsilon)$-fraction of entries of the multiplication $A \cdot B$ of a pair $(A, B)$ of uniformly ... more >>>