BARC talk by Justin Chen 2024

Wednesday, July 31, 2024, Justin Chen, PhD Student at MIT, US, will give a talk on "Profile Estimation in Data Streams ".

Abstract:
A classic paper of Datar and Muthukrishnan from 2002 gave an algorithm to estimate the number of distinct elements that appear i times in a stream (i.e., have frequency i). This problem, referred to as rarity or profile estimation, is widely used in practice and has applications to estimating symmetric functions of the vector of frequencies of elements in a data stream. We give an algorithm which produces estimates of many values of i simultaneously while using less space than prior algorithms. We prove matching lower bounds, showing that our algorithm is space-optimal. Based on joint work with Piotr Indyk and David Woodruff.

Bio:
Justin Chen is a fourth year PhD Student at MIT, advised by Piotr Indyk. In 2020, he received a Bachelors of Science with Honors from Stanford University, working with Greg Valiant. His research interests include streaming and sketching algorithms, differential privacy, and the interface between algorithms and machine learning.

Host: Anders Aamand