License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.555
URN: urn:nbn:de:0030-drops-30433
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3043/
Go to the corresponding LIPIcs Volume Portal

Blaeser, Markus ; Engels, Christian

Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals

pdf-format:
51.pdf (0.6 MB)

Abstract

We construct a hitting set generator for sparse multivariate polynomials over the reals. The seed length of our generator is O(log^2 (mn/epsilon)) where m is the number of monomials, n is number of variables, and 1 - epsilon is the hitting probability. The generator can be evaluated in time polynomial in log m, n, and log 1/epsilon. This is the first hitting set generator whose seed length is independent of the degree of the polynomial. The seed length of the best generator so far by Klivans and Spielman [STOC 2001] depends logarithmically on the degree.

From this, we get a randomized algorithm for testing sparse black box polynomial identities over the reals using O(log^2 (mn/epsilon)) random bits with running time polynomial in log m, n, and log(1/epsilon).

We also design a deterministic test with running time ~O(m^3 n^3). Here, the ~O-notation suppresses polylogarithmic factors. The previously best deterministic test by Lipton and Vishnoi [SODA 2003] has a running time that depends polynomially on log delta, where $delta$ is the degree of the black box polynomial.

BibTeX - Entry

@InProceedings{blaeser_et_al:LIPIcs:2011:3043,
  author =	{Markus Blaeser and Christian Engels},
  title =	{{Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{555--566},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3043},
  URN =		{urn:nbn:de:0030-drops-30433},
  doi =		{10.4230/LIPIcs.STACS.2011.555},
  annote =	{Keywords: Descartes’ rule of signs, polynomial identity testing, sparse polynomials, black box testing}
}

Keywords: Descartes’ rule of signs, polynomial identity testing, sparse polynomials, black box testing
Collection: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue Date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI