Title: The Dynamic Optimality Conjecture
Abstract: Consider the task of performing a sequence of searches in a binary search tree. After each search, an algorithm is allowed to arbitrarily restructure the tree, at a cost proportional to the amount of restructuring performed. The cost of an algorithm’s execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. I will introduce the background and history behind this notion, along with a fascinating set of long-standing conjectures about the behavior of optimal algorithms for performing searches. I will also discuss several existing and recent approaches to solving them.
