Lower bound for the approximative complexity
type: Item
instance of: scholarly article
title: Lower bound for the approximative complexity
zbMATH Open document ID: 0618.68034
DOI: 10.1016/0304-3975(86)90038-1
author: Bernhard Griesser
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: We generalize several methods for obtaining lower bounds for the complexity of polynomials, such as those based on substitution, transcendence degree or algebraic geometric degree, to the approximate model.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 12E05
zbMATH DE Number: 4003519
zbMATH Keywords: lower bounds
zbMATH Keywords: complexity of polynomials
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90038-1
OpenAlex ID: W1965518937
cites work: The complexity of partial derivatives
cites work: Q3280357
cites work: On commutativity and approximation
cites work: Definability and fast quantifier elimination in algebraically closed fields
cites work: A note on the complexity of approximative evaluation of polynomials
cites work: Simple Proofs of Lower Bounds for Polynomial Evaluation
cites work: The Computational Complexity of Continued Fractions
cites work: Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
cites work: On the number of multiplications necessary to compute certain functions
description: scientific article; zbMATH DE number 4003519