Lower bounds for the complexity of polynomials

DOI10.1016/0304-3975(89)90094-7MaRDI QIDQ1822977zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Lower bounds of complexity for polarized polynomials over finite fields
• On lower bounds for the complexity of polynomials and their multiples
• Lower bounds on the bounded coefficient complexity of bilinear maps
• STACS 2005
• Lower bounds on arithmetic circuits via partial derivatives

Cites work

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

Cited in

(28)

• On polynomials with symmetric Galois group which are easy to compute
• Easy lower bound for a strange computational model
• On lower bounds for the complexity of polynomials and their multiples
• Ulrich complexity
• On the representation of rational functions of bounded complexity
• Time-space tradeoffs in algebraic complexity theory
• Lower bounds of complexity for polarized polynomials over finite fields
• Tight worst-case bounds for polynomial loop programs
• scientific article; zbMATH DE number 4172392 (Why is no real title available?)
• Lower bound of the complexity of functions over a finite field of order 4 in the class of polarized polynomials
• scientific article; zbMATH DE number 3860383 (Why is no real title available?)
• Lower bounds on the bounded coefficient complexity of bilinear maps
• scientific article; zbMATH DE number 3974292 (Why is no real title available?)
• scientific article; zbMATH DE number 4047102 (Why is no real title available?)
• scientific article; zbMATH DE number 4070302 (Why is no real title available?)
• scientific article; zbMATH DE number 1222560 (Why is no real title available?)
• scientific article; zbMATH DE number 1760347 (Why is no real title available?)
• Minkowski complexity of sets: an easy lower bound
• scientific article; zbMATH DE number 6829271 (Why is no real title available?)
• Polynomials with Rational Coefficients Which are Hard to Compute
• scientific article; zbMATH DE number 817509 (Why is no real title available?)
• A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
• scientific article; zbMATH DE number 6796098 (Why is no real title available?)
• A new method to obtain lower bounds for polynomial evaluation
• The black-box query complexity of polynomial summation
• On the multiplicative complexity of polynomials
• Lower bounds for polynomials of many variables
• On approximate symmetric polynomials and tightness of homogenization results

This page was built for publication: Lower bounds for the complexity of polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822977)