Theory Lunch Seminar - Meghal Gupta
April 29, 2026 12:00PM—1:00PM
Location:
In Person
-
Gates Hillman 8102
Speaker:
MEGHAL GUPTA,
Ph.D. Student, Department of Electrical Engineering and Computer Sciences, University of California, Berkeley
https://www.meghalgupta.com/
Estimating quantiles is one of the most basic problems in data sketching. In this problem, a stream x1, x2, x3, …, xn of elements from some universe of size U, a rank r, and an accuracy ε are given. The goal is to give a space-efficient algorithm that outputs an element with rank between r-εn and r+εn. For example, this captures median estimation and 99th percentile estimation.
It has long been known that a quantile sketch can be made more space-efficient than storing every element individually (which would take nlogU memory). The previous best algorithms all improved substantially on nlogU but did not meet the lower bound of Ω(ε-1· logεn+logεU)) . In this talk, I’ll describe a deterministic quantile sketch that uses the optimal O(ε-1·(logεn+logεU)) bits of memory.
For More Information:
hfleisch@andrew.cmu.edu