Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HENSEL LIFT:
Reports tagged with Hensel lift:
TR19-008 | 20th January 2019
Ashish Dwivedi, Rajat Mittal, Nitin Saxena

Polynomial factoring has famous practical algorithms over fields-- finite, rational \& $p$-adic. However, modulo prime powers it gets hard as there is non-unique factorization and a combinatorial blowup ensues. For example, $x^2+p \bmod p^2$ is irreducible, but $x^2+px \bmod p^2$ has exponentially many factors! We present the first randomized poly($\deg ... more >>> TR20-077 | 19th May 2020 Amit Sinhababu, Thomas Thierauf #### Factorization of Polynomials Given by Arithmetic Branching Programs 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 ... more >>>

ISSN 1433-8092 | Imprint