Discovering the roots: uniform closure results for algebraic classes under factoring

DOI10.1145/3188745.3188760MaRDI QIDQ5230370zbMATH OpenOpenAlexFDO

Authors Pranjal Dutta, Nitin Saxena, Amit Sinhababu

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1710.03214

zbMATH Keywords

circuit factorizationhardnesspolynomial factorizationroots of polynomials

Mathematics Subject Classification ID

Computational methods for problems pertaining to field theory (12-08) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: Newton iteration (NI) is an almost 350 years old recursive formula that approximates a simple root of a polynomial quite rapidly. We generalize it to a matrix recurrence (allRootsNI) that approximates all the roots simultaneously. In this form, the process yields a better circuit complexity in the case when the number of roots $r$ is small but the multiplicities are exponentially large. Our method sets up a linear system in $r$ unknowns and iteratively builds the roots as formal power series. For an algebraic circuit $f(x_1,ldots,x_n)$ of size $s$ we prove that each factor has size at most a polynomial in: $s$ and the degree of the squarefree part of $f$. Consequently, if $f_1$ is a $2^{Omega(n)}$-hard polynomial then any nonzero multiple $pro{d}_i{f}_i^{e_i}$ is equally hard for arbitrary positive $e_i$'s, assuming that $su{m}_{i}extdeg(f_i)$ is at most $2^{O(n)}$. It is an old open question whether the class of poly($n$)-sized formulas (resp. algebraic branching programs) is closed under factoring. We show that given a polynomial $f$ of degree $n^{O(1)}$ and formula (resp. ABP) size $n^{O(logn)}$ we can find a similar size formula (resp. ABP) factor in randomized poly($n^{logn}$)-time. Consequently, if determinant requires $n^{Omega(logn)}$ size formula, then the same can be said about any of its nonzero multiples. As part of our proofs, we identify a new property of multivariate polynomial factorization. We show that under a random linear transformation $au$, $f(auoverlinex)$ completely factors via power series roots. Moreover, the factorization adapts well to circuit complexity analysis. This with allRootsNI are the techniques that help us make progress towards the old open problems, supplementing the large body of classical results and concepts in algebraic circuit factorization (eg. Zassenhaus, J.NT 1969, Kaltofen, STOC 1985-7 & Burgisser, FOCS 2001).

Recommendations

• Closure results for polynomial factorization
• Factors of low individual degree polynomials
• Factors of low individual degree polynomials
• Univariate polynomials, nearly optimal algorithms for factorization and rootfinding
• scientific article; zbMATH DE number 4128945

Cited in

(10)

• Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
• Factorization of polynomials given by arithmetic branching programs
• A note on VNP-completeness and border complexity
• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• Factorization of polynomials given by arithmetic branching programs
• Closure results for polynomial factorization
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Schur polynomials do not have small formulas if the determinant does not
• Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
• PosSLP and sum of squares

This page was built for publication: Discovering the roots: uniform closure results for algebraic classes under factoring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230370)