Equivalence of polynomial identity testing and polynomial factorization
In this research paper it is demonstrated that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. More specifically, it is explored that, given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial \(f\), the task of computing arithmetic circuits for the factors of \(f\) can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem. Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.
- 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
- 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
- Factoring multivariate polynomials via partial differential equations
- Factoring Polynomials Over Large Finite Fields
- Factoring polynomials with rational coefficients
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- 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?)
- 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
- Deterministic polynomial identity testing in non-commutative models
- On a polytime factorization algorithm for multilinear polynomials over \(\mathbb{F}_2\)
- Blackbox identity testing for sum of special ROABPs and its border class
- Factorization of polynomials given by arithmetic branching programs
- On approximating the eigenvalues of stochastic matrices in probabilistic logspace
- AND-decomposition of Boolean polynomials with prescribed shared variables
- Factors of low individual degree polynomials
- On the relation between polynomial identity testing and finding variable disjoint factors
- A generalized sylvester-gallai type theorem for quadratic polynomials
- Factorization of polynomials given by arithmetic branching programs
- scientific article; zbMATH DE number 7204372 (Why is no real title available?)
- Testing equivalence of polynomials under shifts
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- Derandomizing multivariate polynomial factoring for low degree factors
- On efficient noncommutative polynomial factorization via Higman linearization
- Hitting sets for orbits of circuit classes and polynomial families
- Towards deterministic algorithms for constant-depth factors of constant-depth circuits
- Structural testing with homomorphic encryption
- Graph-based product form
- Uniform bounds on product Sylvester-Gallai configurations
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)
