TALK TITLE: Integral Analysis of Adaptive Algorithms: Real Root Isolation Chee Yap Computer Science Theory Seminar Courant Institute, NYU Jan 24, 2008 ABSTRACT: There is a recent trend to replace algebraic approaches to meshing curves and surfaces by more numerical approaches. The advantage of the such approaches is that they are more practical and has adaptive complexity. However, the complexity analysis of adaptive algorithms is not well understood. There is a similar trend for the 1-D case of meshing, namely, real root isolation: Sturm methods (which is strongly algebraic) are being surplanted by weaker Descartes methods [Rouillier-Zimmermann 2004]. We recently introduce the EVAL algorithm which assumes primitives for function evaluation and interval evaluation. Thus it is applicable a large class of analytic functions. EVAL is the 1-D version of a meshing algorithm from Vegter-Plantinga [2006]. In this talk, we introduce a novel technique to analyze the complexity of EVAL. It is called "integral analysis" because the complexity is expressed as an integral. We use the framework of "stopping functions" its analysis. Suppose f is a square-free polynomial of degree d, with integer coefficients at most L bits. For simplicity, assume L>log d. The "benchmark problem" is to isolated all real zeros of f. For instance, Descartes method has complexity of O(dL) [Eigenwillig, Sharma, Yap 2006], which is optimal. We shall prove that EVAL has complexity O(d^2 L). Integral analysis is a form of "continuous amortization". The amortization comes from Mahler-Davenport type bounds for evaluation of polynomials at algebraic points. Joint work with Michael Burr and Felix Krahmer. ==============================================