Corey Sinnamon will present his Pre-FPO "Improved analysis of self-adjusting heaps" on Wednesday, November 17, 2021 at 11AM via Zoom. Zoom link: https://princeton.zoom.us/my/sinnamon Committee: Examiners: Robert Tarjan (Advisor), Bernard Chazelle, and Maria Chudnovsky. Readers: Huacheng Yu and László Kozma (Freie Universität Berlin). All are welcome to attend the talk. Abstract: Improved analysis of self-adjusting heaps Heaps (priority queues) are a classic and well-studied class of data structures. Among these are self-adjusting heaps, those that take an implicit approach to managing the heap state and require little or no auxiliary data to operate. The pairing heap is the classic example of this, and yet its exact complexity remains unknown, despite decades of study and improved upper and lower bounds. Indeed, we know of no self-adjusting heap that matches the bounds commonly conjectured for pairing heaps. The recently-invented smooth heap is an excellent candidate for an optimal self-adjusting heap. We present analyses of pairing and smooth heaps and their variants, and the challenges that remain for determining their exact complexity.