Factorization of polynomials given by arithmetic branching programs

DOI10.4230/LIPIcs.CCC.2020.33OpenAlexW3046461569MaRDI QIDQ5092484

Amit Sinhababu, Thomas Thierauf

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2020.33

zbMATH Keywords

Newton iterationHensel liftingarithmetic branching programhardness vs randomnessmultivariate polynomial factorization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Schur polynomials do not have small formulas if the determinant does not

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factors of low individual degree polynomials
• Completeness and reduction in algebraic complexity theory
• The complexity of factors of multivariate polynomials
• Equivalence of polynomial identity testing and polynomial factorization
• Algebraic Complexity Classes
• Determinant: Old Algorithms, New Insights
• Discovering the roots: uniform closure results for algebraic classes under factoring
• Proof Complexity Lower Bounds from Algebraic Circuit Complexity
• Derandomizing polynomial identity tests means proving circuit lower bounds

This page was built for publication: Factorization of polynomials given by arithmetic branching programs