Why "1 + 1 < 2" for Space-Efficient Data Structures

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 is a second-year PhD student studying theoretical computer science at CMU, co-advised by William Kuszmaul and Guy Blelloch. He completed his Bachelor's degree in Yao Class at Tsinghua University. He mainly works on classical data structures, especially hash tables and succinct data structures. He is also known for his work on fast matrix multiplication.

Room

Room 602