Joint Theory Lunch Seminar / Speaking Skills Talk - Jingxun Liang

— 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

Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries

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