License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.943
URN: urn:nbn:de:0030-drops-53469
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5346/
Go to the corresponding LIPIcs Volume Portal

Volkovich, Ilya

Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials

pdf-format:
56.pdf (0.5 MB)

Abstract

We present the first efficient deterministic algorithm for factoring sparse polynomials that split into multilinear factors
and sums of univariate polynomials. Our result makes partial progress towards the resolution of the classical question posed by von zur Gathen and Kaltofen in [von zur Gathen/Kaltofen, J. Comp. Sys. Sci., 1985] to devise an efficient deterministic algorithm for factoring (general) sparse polynomials. We achieve our goal by introducing essential factorization schemes which can be thought of as a relaxation of the regular factorization notion.

BibTeX - Entry

@InProceedings{volkovich:LIPIcs:2015:5346,
  author =	{Ilya Volkovich},
  title =	{{Deterministically Factoring Sparse Polynomials into Multilinear Factors and Sums of Univariate Polynomials}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{943--958},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Naveen Garg and Klaus Jansen and Anup Rao and Jos{\'e} D. P. Rolim},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5346},
  URN =		{urn:nbn:de:0030-drops-53469},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.943},
  annote =	{Keywords: Derandomization, Multivariate Polynomial Factorization, Sparse polynomials}
}

Keywords: Derandomization, Multivariate Polynomial Factorization, Sparse polynomials
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Issue Date: 2015
Date of publication: 13.08.2015

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