Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-077 | 19th May 2020 16:36

Factorization of Polynomials Given by Arithmetic Branching Programs

RSS-Feed




TR20-077
Authors: Amit Sinhababu, Thomas Thierauf
Publication: 19th May 2020 16:47
Downloads: 1122
Keywords: 


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 $\text{poly}(s)$. Kaltofen gave a similar result for polynomials computed by arithmetic circuits. The previously known best upper bound for ABP-factors was $\text{poly}(s^{\log s}) $.



ISSN 1433-8092 | Imprint