MPI-INF/SWS Research Reports 1991-2021

2. Number - All Departments


Generalized and improved constructive separation bound for real algebraic expressions

Mehlhorn, Kurt and Schirra, Stefan

November 2000, 12 pages.

Status: available - back from printing

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.}

  • Attachement: (114 KBytes)

URL to this document:

Hide details for BibTeXBibTeX
  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},