Abstract

In this talk, we show the first example of the following surprising phenomenon: For two completely independent data structure problems A and B, solving A and B together can be done in a more space-efficient way than solving A and B separately. To prove such a phenomenon, we determine the optimal time-space trade-off for retrieval data structures and its variants, and our results have an important application in static dictionaries.

Time

2025-12-24  14:00 - 15:00

Speaker

Renfei Zhou, CMU

Room

Room 602