Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Sinhababu, Amit; Thierauf, Thomas https://www.dagstuhl.de/lipics License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-125854
URL:

;

Factorization of Polynomials Given By Arithmetic Branching Programs

pdf-format:


Abstract

Given a multivariate polynomial computed by an arithmetic branching program (ABP) of size s, we show that all its factors can be computed by arithmetic branching programs of size poly(s). Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was poly(s^(log s)).

BibTeX - Entry

@InProceedings{sinhababu_et_al:LIPIcs:2020:12585,
  author =	{Amit Sinhababu and Thomas Thierauf},
  title =	{{Factorization of Polynomials Given By Arithmetic Branching Programs}},
  booktitle =	{35th Computational Complexity Conference (CCC 2020)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-156-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{169},
  editor =	{Shubhangi Saraf},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12585},
  URN =		{urn:nbn:de:0030-drops-125854},
  doi =		{10.4230/LIPIcs.CCC.2020.33},
  annote =	{Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness}
}

Keywords: Arithmetic Branching Program, Multivariate Polynomial Factorization, Hensel Lifting, Newton Iteration, Hardness vs Randomness
Seminar: 35th Computational Complexity Conference (CCC 2020)
Issue date: 2020
Date of publication: 17.07.2020


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