2026-07-23T05:17:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12585 2024-03-06T10:50:31Z ddc:004 open_access

Factorization of Polynomials Given By Arithmetic Branching Programs Sinhababu, Amit Thierauf, Thomas Arithmetic Branching Program Multivariate Polynomial Factorization Hensel Lifting Newton Iteration Hardness vs Randomness 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)). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amit Sinhababu and Thomas Thierauf 2020 Is Part Of LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2020.33 urn:nbn:de:0030-drops-125854 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.33 eng https://creativecommons.org/licenses/by/3.0/legalcode