Joint Theory Lunch Seminar / Speaking Skills Talk - Jingxun Liang January 29, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: JINGXUN LIANG, Ph.D. Student, Computer Science Department, Carnegie Mellon University https://sites.google.com/view/jingxun/home The dictionary problem involves maintaining a set S ⊂ [U] of n keys under insertions, deletions, and membership queries focusing on efficiency in both time and space. This fundamental problem has been studied extensively for six decades since 1953. Recently, a series of works has established the optimal time-space trade-off for dictionaries. In this talk, I will describe the tight lower bound result that any dictionary with an operational time t just incur a redundant Ω(log(t) n) bits per key in space. Presented as part of the Theory Lunch Seminar Presented in Partial Fulfillment of the CSD Speaking Skills Requirement Event Website: https://www.cs.cmu.edu/~theorylunch/ Add event to Google Add event to iCal
