Lower bounds for polynomials with algebraic coefficients

DOI10.1016/0304-3975(80)90019-5zbMath0452.68051OpenAlexW1977747221MaRDI QIDQ1148670

Malte Sieveking, Joos Heintz

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90019-5

zbMATH Keywords

polynomial evaluationsolution of linear equations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10) Linear equations (linear algebraic aspects) (15A06)

Related Items

On Kolmogorov complexity in the real Turing machine setting, On polynomials with symmetric Galois group which are easy to compute, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz, Simplified lower bounds for polynomials with algebraic coefficients, Feasible arithmetic computations: Valiant's hypothesis, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Some polynomials that are hard to compute, On the additive complexity of polynomials, Invariant and geometric aspects of algebraic complexity theory. I, Time-space tradeoffs in algebraic complexity theory, A new method to obtain lower bounds for polynomial evaluation, Unnamed Item, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, On the representation of rational functions of bounded complexity, Lower bounds in algebraic computational complexity, Definability and fast quantifier elimination in algebraically closed fields, Unifying known lower bounds via geometric complexity theory, On the algebraic complexity of rational iteration procedures

Cites Work

• On the additive complexity of polynomials
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• On the Number of Additions to Compute Specific Polynomials
• Polynomials with Rational Coefficients Which are Hard to Compute
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item