Electronic Proceedings Article @InProceedings Internet-Beitrag in Tagungsband, Workshop

 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor
 Author(s): Eigenwillig, Arno Sharma, Vikram Yap, Chee K. dblp dblp dblp Not MPG Author(s): Sharma, Vikram Yap, Chee K.
 Editor(s): Dumas, Jean-Guillaume dblp Not MPII Editor(s): Dumas, Jean-Guillaume
 BibTeX cite key*: Eigenwillig2006a

 Title, Conference
 Title*: Almost Tight Recursion Tree Bounds for the Descartes Method ESY-DescTree-ISSAC06-authprep.pdf (183.17 KB) Booktitle*: ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation Event Address*: Genova, Italy URL of the conference: http://issac2006.dima.unige.it/ Event Date*: (no longer used): URL for downloading the paper: http://doi.acm.org/10.1145/1145768.1145786 Event Start Date: 9 July 2006 Event End Date: 12 July 2006 Language: English Organization: Association for Computing Machinery (ACM)

 Publisher
 Publisher's Name: ACM Publisher's URL: http://www.acm.org/ Address*: New York, USA Type:

 Vol, No, pp., Year
 Series: Volume: Number: Month: July Pages: 71-78 Sequence Number: Year*: 2006 ISBN/ISSN: 1-59593-276-3

 URL for Reference: Note: (LaTeX) Abstract: We give a unified ("basis free") framework for the Descartes method for real root isolation of square-free real polynomials. This framework encompasses the usual Descartes' rule of sign method for polynomials in the power basis as well as its analog in the Bernstein basis. We then give a new bound on the size of the recursion tree in the Descartes method for polynomials with real coefficients. Applied to polynomials $A(X) = \sum_{i=0}^n a_iX^i$ with integer coefficients $\abs{a_i} < 2^L$, this yields a bound of $O(n(L + \log n))$ on the size of recursion trees. We show that this bound is tight for $L = \Omega(\log n)$, and we use it to derive the best known bit complexity bound for the integer case. URL for the Abstract: Tags, Categories, Keywords: Polynomial real root isolation, Descartes method, Descartes rule of signs, Bernstein basis, Davenport-Mahler bound HyperLinks / References / URLs: http://doi.acm.org/10.1145/1145768.1145786 Copyright Message: Copyright (c) ACM, 2006. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation (ISSAC 2006), http://doi.acm.org/10.1145/1145768.1145786 Personal Comments: The title on the printed proceedings volume is "...and Algebraic Computations", but according to (i) grammar, (ii) previous proceedings volumes, and (iii) the ACM Digital Library, the final "s" is wrong and should be deleted. Download Access Level: Public

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
@INPROCEEDINGS{Eigenwillig2006a,
AUTHOR = {Eigenwillig, Arno and Sharma, Vikram and Yap, Chee K.},
EDITOR = {Dumas, Jean-Guillaume},
TITLE = {Almost Tight Recursion Tree Bounds for the {D}escartes Method},
BOOKTITLE = {ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computation},
PUBLISHER = {ACM},
YEAR = {2006},
ORGANIZATION = {Association for Computing Machinery (ACM)},
PAGES = {71--78},