Theory Lunch Seminar - Hanna Komlos April 9, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: HANNA KOMLOS , Ph.D. Student in Theoretical Computer Science, Computer Science and Engineering, Tandom School of Engineering, New York University https://www.hannakomlos.com/ Online List Labeling: Near optimality through hiding and exploiting the history of operations This talk focuses on the list-labeling problem, a fundamental data structural primitive with a long history of both theoretical study and practical application. List labeling captures the basic task of storing a dynamically changing set of up to N elements in sorted order in an array of size M=Θ(N). The goal is to support online insertions and deletions while moving elements around in the array as little as possible. Despite over four decades of study, there has until recently been a longstanding gap between the upper and lower bounds for list labeling (O(log^2(N)) and Ω(log(N)) element moves per operation, respectively). Two recent breakthroughs have closed this gap to within polylogarithmic factors. In a paper at FOCS 2022, we give a randomized algorithm which uses the traditional data structural security property of history independence to hide information from an oblivious adversarial inserter in order to achieve an improved O(log^1.5(N)) worst-case expected cost. In a FOCS 2024 paper, we build a randomized predictor of future operations from a workload’s history that performs well on all inputs in expectation. Combining this with a prediction-augmented algorithm, we achieve a further improved worst-case upper bound of Õ(log(N)). To the best of our knowledge, this is the first example of an application of the algorithms-with-predictions framework that uses an internal predictor to achieve a better worst-case upper bound. Event Website: https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20250409.html Add event to Google Add event to iCal
