Equivalence of polynomial identity testing and polynomial factorization

DOI10.1007/s00037-015-0102-yzbMath1319.65035OpenAlexW2111727595MaRDI QIDQ2351391

Amir Shpilka, Swastik Kopparty, Shubhangi Saraf

Publication date: 23 June 2015

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0102-y

zbMATH Keywords

algorithmpolynomial factorizationmultivariate polynomialarithmetic complexityarithmetic circuitspolynomial identity testing

Mathematics Subject Classification ID

Polynomials in real and complex fields: factorization (12D05) Numerical computation of roots of polynomial equations (65H04) Numerical algorithms for computer arithmetic, etc. (65Y04)

Related Items (11)

Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Factors of low individual degree polynomials ⋮ On approximating the eigenvalues of stochastic matrices in probabilistic logspace ⋮ Sylvester-Gallai type theorems for quadratic polynomials ⋮ On the complexity of noncommutative polynomial factorization ⋮ AND–Decomposition of Boolean Polynomials with Prescribed Shared Variables ⋮ Blackbox identity testing for sum of special ROABPs and its border class ⋮ Unnamed Item ⋮ Factorization of polynomials given by arithmetic branching programs ⋮ A generalized sylvester-gallai type theorem for quadratic polynomials ⋮ Factorization of polynomials given by arithmetic branching programs

Cites Work

• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Matching is as easy as matrix inversion
• Factoring polynomials with rational coefficients
• A probabilistic remark on algebraic program testing
• PRIMES is in P
• Effective Noether irreducibility forms and applications
• Arithmetic Circuits: A Chasm at Depth 3
• Arithmetic Circuits: A survey of recent results and open questions
• Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
• On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Factoring multivariate polynomials via partial differential equations
• Factoring Polynomials Over Large Finite Fields
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Equivalence of polynomial identity testing and polynomial factorization