On the representation of rational functions of bounded complexity

DOI10.1016/0304-3975(89)90093-5zbMath0679.68099OpenAlexW2097928936MaRDI QIDQ1822978

Hans-Jörg Stoß

Publication date: 1989

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

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

zbMATH Keywords

rational functionslower complexity boundsRepresentation Theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General field theory (12E99)

Related Items

On the efficiency of effective Nullstellensätze, Time-space tradeoffs in algebraic complexity theory, A Gröbner free alternative for polynomial system solving, A new method to obtain lower bounds for polynomial evaluation, Lower bounds for the complexity of polynomials, Complexity bounds in elimination theory -- a survey., An effective algorithm for quantifier elimination over algebraically closed fields using straight line programs, The Projective Noether Maple Package: Computing the dimension of a projective variety

Cites Work

• Unnamed Item
• Some polynomials that are hard to compute
• Lower bounds for polynomials with algebraic coefficients
• On the additive complexity of polynomials
• Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials
• Lower bounds for the complexity of polynomials
• Berechnung und Programm. I
• 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