摘要：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)).
关键词：Arithmetic Branching Program; Multivariate Polynomial Factorization; Hensel Lifting; Newton Iteration; Hardness vs Randomness
