Equivalence of polynomial identity testing and polynomial factorization

DOI10.1007/S00037-015-0102-YMaRDI QIDQ2351391zbMATH OpenOpenAlexFDO

Authors Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

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

algorithmarithmetic circuitspolynomial identity testingmultivariate polynomialpolynomial factorizationarithmetic complexity

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)

Recommendations

• On the relation between polynomial identity testing and finding variable disjoint factors
• scientific article; zbMATH DE number 2079409
• Progress on polynomial identity testing
• scientific article; zbMATH DE number 1033920
• Irreducibility Testing and Factorization of Polynomials
• Read-once polynomial identity testing
• Read-once polynomial identity testing
• Recent results on polynomial identity testing
• Progress on polynomial identity testing. II
• scientific article; zbMATH DE number 7758310

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 15339 (Why is no real title available?)
• scientific article; zbMATH DE number 2151173 (Why is no real title available?)
• A probabilistic remark on algebraic program testing
• Arithmetic circuits: a chasm at depth 3
• Arithmetic circuits: a survey of recent results and open questions
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Effective Noether irreducibility forms and applications
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Factoring Polynomials Over Large Finite Fields
• Factoring multivariate polynomials via partial differential equations
• Factoring polynomials with rational coefficients
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Hardness-randomness tradeoffs for bounded depth arithmetic circuits
• Matching is as easy as matrix inversion
• Modern computer algebra
• On the relation between polynomial identity testing and finding variable disjoint factors
• PRIMES is in P

Cited in

(13)

• scientific article; zbMATH DE number 7204372 (Why is no real title available?)
• Factors of low individual degree polynomials
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Factorization of polynomials given by arithmetic branching programs
• Blackbox identity testing for sum of special ROABPs and its border class
• Factorization of polynomials given by arithmetic branching programs
• On a polytime factorization algorithm for multilinear polynomials over \(\mathbb{F}_2\)
• AND-decomposition of Boolean polynomials with prescribed shared variables
• On the relation between polynomial identity testing and finding variable disjoint factors
• Deterministic polynomial identity testing in non-commutative models
• A generalized sylvester-gallai type theorem for quadratic polynomials
• Testing equivalence of polynomials under shifts

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

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