The complexity of factors of multivariate polynomials

DOI10.1007/S10208-002-0059-5MaRDI QIDQ1764397zbMATH OpenOpenAlexFDO

Authors Peter Bürgisser

Publication date 24 February 2005

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

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(17)

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

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)