Online List Labeling

Online List Labeling (via Zoom)

Abstract:  The online list-labeling problem is a classical combinatorial problem with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically changing set of n items in an array of m slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. There has long existed a gap between the lower and upper bounds in the most algorithmically interesting part of the problem's parameter space. In this talk, I’ll should how we narrowed this gap for the first time in nearly 4 decades. Additionally, I will describe some recent results on composing multiple list-labeling algorithms in order to obtain the best combination of their respective cost guarantees.

Bio: Alex Conway is an assistant professor at Cornell Tech. His work has primarily focused on randomized data structures and their use in storage and memory systems, and covers the full research stack, from theory to systems to product. Prior to Cornell, he was a senior researcher at VMware. He received his PhD from Rutgers, where he was advised by Martín Farach-Colton. He is the co-creator and research lead of SplinterDB, an enterprise-grade key-value store deployed in VMware products.