DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2011.428

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}
}

Search Results

Documents authored by Uurtamo, Steve

Polynomial Fitting of Data Streams with Applications to Codeword Testing

Abstract

Cite as

Thanks for your feedback!

Could not send message