TCS Seminar - Improved Lower Bounds for Privacy under Continual Release
Date
Thursday, March 26, 2026 11:30 - 12:30
Speaker
Bardiya Aryanfard (ISTA)
Location
Moonstone Bldg / Ground floor / Seminar Room C (I24.EG.030c)
Series
Seminar/Talk
Contact
In the continual observation model of differential privacy, problems are generally considered easy if they admit an additive error polylogarithmic in the stream length T and the universe size n. Conversely, problems that require additive error polynomial in n and T are considered difficult. Recently, Raskhodikova and Steiner (PODS 25) proved polynomial lower bounds on the additive error of many graph problems under fully dynamic edge differential privacy. This raises a natural question: are these problems difficult even in the insertions-only model, or does their hardness arise strictly from the fully dynamic setting?
We show that for many problems, the former is true. We prove polynomial lower bounds for a variety of these problems (e.g., maximum matching) in the insertions-only setting. We then extend our techniques to the problem of estimating all symmetric norms simultaneously (SNE), providing the first polynomial lower bound for this problem.
Based on joint work with Monika Henzinger, David Saulpic, and A. R. Sricharan (https://arxiv.org/abs/2512.15981, to appear in PODS 26)