Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-077 | 19th May 2020 16:36

#### Factorization of Polynomials Given by Arithmetic Branching Programs

TR20-077
Authors: Amit Sinhababu, Thomas Thierauf
Publication: 19th May 2020 16:47
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})$.