MPI-INF D1 Publications: Electronic Proceedings Article: Almost Tight Recursion Tree Bounds for the {D}escartes Method

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

Show entries of:

this year (2023) | last year (2022) | two years ago (2021) | Notes URL

Action:

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
Attachment(s):	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

Abstract, Links, ©

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},
ADDRESS = {Genova, Italy},
MONTH = {July},
ISBN = {1-59593-276-3},
}

Entry last modified by Uwe Brahm, 04/27/2007

Edit History (please click the blue arrow to see the details)

	Editor(s) Arno Eigenwillig	Created 07/21/2006 13:46:07
Revisions 5. 4. 3. 2. 1.	Editor(s) Uwe Brahm Arno Eigenwillig Christine Kiesel Christine Kiesel Christine Kiesel	Edit Dates 2007-04-27 18:33:58 03/17/2007 05:26:19 PM 07.02.2007 11:23:34 07.02.2007 11:22:43 07/21/2006 01:47:15 PM

Attachment Section

ESY-DescTree-ISSAC06-authprep.pdf

ESY-DescTree-ISSAC06-authprep.pdf