Search Results

Documents authored by Uurtamo, Steve


Document
Polynomial Fitting of Data Streams with Applications to Codeword Testing

Authors: Andrew McGregor, Atri Rudra, and Steve Uurtamo

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)


Abstract
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.

Cite as

Andrew McGregor, Atri Rudra, and Steve Uurtamo. Polynomial Fitting of Data Streams with Applications to Codeword Testing. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 428-439, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{mcgregor_et_al:LIPIcs.STACS.2011.428,
  author =	{McGregor, Andrew and Rudra, Atri and Uurtamo, Steve},
  title =	{{Polynomial Fitting of Data Streams with Applications to Codeword Testing}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{428--439},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.428},
  URN =		{urn:nbn:de:0030-drops-30322},
  doi =		{10.4230/LIPIcs.STACS.2011.428},
  annote =	{Keywords: Streaming, Polynomial Interpolation, Polynomial Regression}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail