Lower bounds for the complexity of polynomials

DOI10.1016/0304-3975(89)90094-7zbMath0679.68098OpenAlexW2142928190MaRDI QIDQ1822977

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)90094-7

zbMATH Keywords

lower boundspolynomials with 0-1-coefficients

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polynomials in general fields (irreducibility, etc.) (12E05)

Related Items

Time-space tradeoffs in algebraic complexity theory ⋮ On the representation of rational functions of bounded complexity

Cites Work

• On polynomials with symmetric Galois group which are easy to compute
• On the additive complexity of polynomials
• Evaluation of polynomials with super-preconditioning
• On the representation of rational functions of bounded complexity
• An Algorithm for the Computation of Linear Forms
• On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials