Abstract

In this talk, we show the first example of the following surprising pheonmenon: 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

Wednesday, Dec. 24, 14:00--15:00

Speaker

Renfei Zhou

Room

Room 602