Please note: This seminar will take place in DC 1304 and online.
Bardiya Aryanfard, PhD student
Institute of Science and Technology Austria
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, to appear in PODS ‘26.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.