The complexity of factors of multivariate polynomials

DOI10.1007/S10208-002-0059-5zbMATH Open1061.68064arXiv1812.06828OpenAlexW3125711786MaRDI QIDQ1764397FDOQ1764397

Authors: Peter Bürgisser 

Publication date: 24 February 2005

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: The existence of string functions, which are not polynomial time computable, but whose graph is checkable in polynomial time, is a basic assumption in cryptography. We prove that in the framework of algebraic complexity, there are no such families of polynomial functions of polynomially bounded degree over fields of characteristic zero. The proof relies on a polynomial upper bound on the approximative complexity of a factor g of a polynomial f in terms of the (approximative) complexity of f and the degree of the factor g. This extends a result by Kaltofen (STOC 1986). The concept of approximative complexity allows to cope with the case that a factor has an exponential multiplicity, by using a perturbation argument. Our result extends to randomized (two-sided error) decision complexity.

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

Recommendations

• scientific article; zbMATH DE number 799766
• Irreducibility of multivariate polynomials
• Closure results for polynomial factorization
• scientific article; zbMATH DE number 988157
• Factors of low individual degree polynomials

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polynomials, factorization in commutative rings (13P05)

Cited In (17)

• Title not available (Why is that?)
• On polynomials with symmetric Galois group which are easy to compute
• Title not available (Why is that?)
• On the complexity of the computation of certain classes of polynomials of several variables
• A note on VNP-completeness and border complexity
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• Interpolation in Valiant's theory
• Factorization of polynomials given by arithmetic branching programs
• Unifying known lower bounds via geometric complexity theory
• Open problems in deformations of Artinian algebras, Hilbert schemes and around
• Factorization of polynomials given by arithmetic branching programs
• Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing
• No occurrence obstructions in geometric complexity theory
• Geometric complexity theory. V: Efficient algorithms for Noether normalization
• Computation of simple and group factors of multivariate polynomials
• Title not available (Why is that?)
• Weighted sum-of-squares lower bounds for univariate polynomials imply \(\mathsf{VP} \neq \mathsf{VNP}\)

This page was built for publication: The complexity of factors of multivariate polynomials

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