MPI-I-2000-1-004

Generalized and improved constructive separation bound for real algebraic expressions

Mehlhorn, Kurt and Schirra, Stefan

MPI-I-2000-1-004. November 2000, 12 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:

We prove a separation bound for a large class of algebraic expressions
specified by expression dags.
The bound applies to expressions whose leaves are integers
and whose internal nodes are additions, subtractions, multiplications,
divisions, $k$-th root operations for integral $k$, and taking roots of
polynomials whose coefficients are given by the values of subexpressions.
The (logarithm of the)
new bound depends linearly on the algebraic degree of the expression.
Previous bounds applied to a smaller class of expressions and did not
guarantee linear dependency.
\ignore{In~\cite{BFMS} the dependency was quadratic.
and in the Li-Yap bound~\cite{LY} the dependency is usually linear, but may be
even worse than quadratic.}

Acknowledgement:
References to related material:

To download this research report, please select the type of document that fits best your needs.	Attachement Size(s):
	114 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/2000-1-004

BibTeX
@TECHREPORT{MehlhornSchirra2000, AUTHOR = {Mehlhorn, Kurt and Schirra, Stefan}, TITLE = {Generalized and improved constructive separation bound for real algebraic expressions}, TYPE = {Research Report}, INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik}, ADDRESS = {Stuhlsatzenhausweg 85, 66123 Saarbr{\"u}cken, Germany}, NUMBER = {MPI-I-2000-1-004}, MONTH = {November}, YEAR = {2000}, ISSN = {0946-011X},}