Given a stream of (x,y) points, we consider the problem of finding univariate
polynomials that best fit the data. Over finite fields, this problem encompasses
the well-studied problem of decoding Reed-Solomon codes while over the reals it
corresponds to the well-studied polynomial regression problem.

We present one-pass algorithms for two natural problems: i) find the
polynomial of a given degree k that minimizes the error and ii) find the
polynomial of smallest degree that interpolates through the points with at most a
given error bound. We consider a range of error models including the average
error per point, the maximum error, and the number of points that are not fitted
exactly. Many of our results apply to both the reals and finite fields. As a
consequence we also solve an open question regarding the tolerant testing of codes in
the data stream model.