Static Retrieval Revisited: To Optimality and Beyond
Wednesday, May 6, 2026 - 4:00pm to 5:00pm
Location:
32-G575
Speaker:
Bill Kuszmaul (Carnegie Mellon)
Biography:
https://sites.google.com/site/williamkuszmaul/
Seminar group:
In this talk, we settle a classic open question in space-efficient data structures: the number of bits required to encode a key-value retrieval function that supports efficient queries. Along the way, we uncover a surprising phenomenon: the existence of two completely independent problems A and B such that a data structure solving A and B together (with shared memory) can achieve provably better space/time bounds than any pair of data structures solving A and B individually.
Talk is based on this paper at FOCS 25.