Adaptive Analysis of Algorithms
Erik D. Demaine
MIT
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.
