BARC talk by Tamalika Mukherjee 2024

Tuesday, August 27, 2024, Tamalika Mukherjee, Postdoc at Columbia University, US, will give a talk on "Differential privacy and Sublinear time are incompatible sometimes".

Abstract:
Differential privacy and sublinear algorithms are both rapidly emerging algorithmic themes in times of big data analysis. Although recent works have shown the existence of differentially private sublinear algorithms for many problems including graph parameter estimation and clustering, little is known regarding hardness results on these algorithms. In this paper, we initiate the study of lower bounds for problems that aim for both differentially-private and sublinear-time algorithms. Our main result is the incompatibility of both the desiderata in the general case. In particular, we prove that a simple problem based on one-way marginals yields both a differentially-private algorithm, as well as a sublinear-time algorithm, but does not admit a “strictly” sublinear-time algorithm that is also differentially private.

Bio:
Tamalika Mukherjee is a Postdoctoral Research Scientist at Columbia University. She completed her Ph.D. at Purdue University, where she was awarded the Bilsland Dissertation Fellowship. During her Ph.D. she was also a Research Intern at Analog Devices and a Student Researcher at Google Research. Her current research explores the intersection of data privacy and theoretical computer science and its impact on society.

Host:
Rasmus Pagh