Adaptive Analysis of Algorithms

Erik D. Demaine
MIT

Friday, February 16th, 2007, 3:30 pm
Wean Hall 7220

Abstract

For many computational problems, some inputs are easier than others. How can we tell easy inputs from hard inputs? Worst-case analysis of algorithms is often unsatisfying because it misses these performance nuances. Average-case analysis gives a better sense about possible performance, but requires some knowledge about the distribution of inputs, making results more specific. In contrast, adaptive analysis parameterizes the input space by one or more additional parameters beyond the problem size, and the goal becomes to optimize simultaneously for all values of those parameters, which is a substantially stronger form of worst-case analysis. When possible, strong adaptive bounds give a fine sense of the intrinsic difficulty of inputs and a better sense of which algorithms are better than which others.

In particular, I'll talk about successful adaptive analyses of algorithms for boolean set operations (arising in text retrieval), black-box curve manipulation (arising in computer-aided design), black-box function integration (arising in numerical analysis), and basic problems such as sorting and binary search trees.

Bio

Erik Demaine is Associate Professor and Esther and Harold E. Edgerton Professor in computer science at the Massachusetts Institute of Technology. Demaine's research interests range throughout algorithms, from data structures for improving web searches to the geometry of understanding how proteins fold to the computational difficulty of playing games. He received a MacArthur Fellowship (2003) as a "computational geometer tackling and solving difficult problems related to folding and bending--moving readily between the theoretical and the playful, with a keen eye to revealing the former in the latter." He just completed a book about folding together with Joseph O'Rourke, called Geometric Folding Algorithms: Linkages, Origami, and Polyhedra, to be published this summer with Cambridge University Press. He has also coedited "Tribute to a Mathemagician" (A K Peters, 2003), in honor of the influential mathemagician Martin Gardner.