The complexity of factors of multivariate polynomials

DOI10.1007/S10208-002-0059-5zbMath1061.68064arXiv1812.06828OpenAlexW3125711786MaRDI QIDQ1764397

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

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

Related Items (15)

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

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