Caleb Levy will present his FPO "New Paths from Splay to Dynamic Optimality" on Wednesday, May 15, 2019 at 2pm in Fine Hall 224. The members of his committee are as follows: Advisor: Robert Tarjan Non-Readers: Bernard Chazelle and Robert Sedgewick Readers: Kurt Mehlhorn ( Max-Planck-Institut fur Informatik) 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 execution is the sum of the time spent searching and the time spent optimizing those searches with restructuring operations. This notion was introduced by Sleator and Tarjan in 1985, along with an algorithm and a conjecture. The algorithm, Splay, is an elegant procedure for performing adjustments while moving searched items to the top of the tree. The conjecture, called dynamic optimality, is that the cost of splaying is always within a constant factor of the optimal algorithm for performing searches. The conjecture stands to this day. We make the following contributions to this problem: 1. We introduce simulation embeddings: mappings from executions to lists of keys that induce target algorithms to simulate the executions. We build a simulation embedding for Splay by inducing Splay to perform arbitrary subtree transformations, and show that if the cost of splaying a sequence of items is an upper bound on the cost of splaying every subsequence thereof to within a constant factor, then Splay is dynamically optimal. We call this property approximate monotonicity. We also show that approximate monotonicity is a necessary condition for dynamic optimality. 2. We show that if Splay is dynamically optimal, then with respect to optimal costs, its additive overhead is at most linear in the sum of initial tree size and number of requests. 3. We prove that Wilber’s lower bound on optimal execution cost is approximately monotone. 4. Drawing on extensive empirical and heuristic observations, we speculate about how one might establish dynamic optimality by adapting the proof of monotonicity from the crossing lower bound to Splay. 5. We show that several related conjectures also follow if Splay is approximately monotone, and demonstrate that most of the results in this paper extend to a broader class of “path-based” algorithms. It is hoped that this work lays the foundations for a final proof of the dynamic optimality conjecture. A copy of this thesis is available upon request.