Next: Adaptively Secure Multi-party Computation
Up: The First 1.5 Years
Previous: Free Bits, PCPs and
This paper presents an algorithm for reconstructing
all n-variant polynomials of degree d,
over a finite field F, that agree with a given function
on a given (small) fraction of the domain.
Given oracle access to the function,
the algorithm operates in time polynomailly related
to n and the agreement parameter and exponential in d,
provided that the agreement parameter is above some bound
that refers to the ratio of the degree and the field size.
Comments:
Authored by O. Goldreich, R. Rubinfeld and M. Sudan. Appeared in
- Proc. of the 36th FOCS, pp. 294-303, 1995.
- SIAM
J. on Disc. Math., Vol. 13, No. 4, pages 535-570, 2000.
Oded Goldreich
2003-07-30