๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Complexity Lower Bounds for Approximation Algebraic Computation Trees

โœ Scribed by Felipe Cucker; Dima Grigoriev

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
159 KB
Volume
15
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

โœฆ Synopsis

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.

๐Ÿ“œ SIMILAR VOLUMES

Nearly Sharp Complexity Bounds for Multi
Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations
โœ Dima Grigoriev ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 273 KB

The complexity lower bound of ( p log N) was obtained [12,14] for recognizing a semialgebraic set with N connected components by some parallel computational models, like the accepting network or the algebraic PRAM. It is unknown whether a parallel computation has an advantage versus its sequential c

Some Lower Bounds for the Complexity of
Some Lower Bounds for the Complexity of Continuation Methods
โœ Jean-Pierre Dedieu; Steve Smale ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 222 KB

In this note we consider the zero-finding problem for a homogeneous polynomial system, The well-determined (m=n) and underdetermined (m<n) cases are considered together. We also let D=max d i , d=(d 1 , ..., d m ), and The projective Newton method has been introduced by Shub in [6] and is defined

Folded Tilting Complexes for Brauer Tree
Folded Tilting Complexes for Brauer Tree Algebras
โœ Jeremy Rickard; Mary Schaps ๐Ÿ“‚ Article ๐Ÿ“… 2002 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 144 KB

We give dual one-sided tilting complexes producing inverse equivalences of the derived category of a Brauer star algebra and a Brauer tree algebra of the same type, folded according to an additional combinatorial structure on the Brauer tree. We relate this to the two-sided two-term tilting complex