What are some results on algorithms that estimate polynomials over a given set of points?
Not really what you asked for, but your question was a bit open, so maybe this will interest you.

For the specific problem of estimating infinite polynomials (generating functions), $A(z) = \sum_{n=0}^\infty a_n z^n$, with a combinatorial origin, there is a recently published paper, "Algorithms for combinatorial structures: Well-founded systems and Newton iterations" by Pivoteau, Salvy and Soria. I believe (though I might be slightly off) it shows that approximations can be computed in complexity that is quadratic in the required precision. The set of points is the radius of convergence, and in particular the singularity of the generating function.