@article{22318,
  abstract     = {Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously
over a long period of time, making more statistical releases as either queries come in or the dataset is updated.
In this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that
support dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion
of neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition
theorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries
and dataset updates to the different composed mechanisms. Previous concurrent composition theorems for
differential privacy were only for the case when the dataset is static, with no adaptive updates. We also give
the first interactive and continual generalizations of the “parallel composition theorem” for noninteractive
differential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem
holds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure
differential privacy, but it fails to hold for composing approximately differentially private mechanisms with
dataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent
filter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We
extend these results to other measures of differential privacy, including Rényi DP and 𝑓 -DP.
We then formalize a set of general conditions on a continual mechanism M that runs multiple continual submechanisms such that the privacy guarantees of M follow directly using the above concurrent composition
theorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular
privacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the
case of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.
We also provide a framework that simplifies the analysis of local differential privacy when the protocol
includes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core
decomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5].},
  author       = {Henzinger, Monika H and Safavi Hemami, Roodabeh and Vadhan, Salil},
  issn         = {2836-6573},
  journal      = {Proceedings of the ACM on Management of Data},
  keywords     = {differential privacy, concurrent composition, continual release, continual observation, data streaming, continual mechanisms, concurrent parallel composition, concurrent filter composition},
  number       = {2},
  pages        = {1--26},
  publisher    = {Association for Computing Machinery},
  title        = {{Concurrent composition for differentially private continual mechanisms}},
  doi          = {10.1145/3801895},
  volume       = {4},
  year         = {2026},
}

@article{22322,
  abstract     = {We study the problem of continually releasing statistics of an evolving dataset under differential privacy. In the event-level setting, we show the first polynomial lower bounds on the additive error for insertions-only graph problems such as maximum matching, degree histogram and k-core number computation. These results represent an exponential improvement on the polylogarithmic lower bounds of Fichtenberger, Henzinger and Ost [ESA 2021] for the former two problems, and are the first lower bounds in the continual release setting for the latter problem. Our results run counter to the intuition that the difference between insertions-only vs fully dynamic updates causes the gap between polylogarithmic and polynomial additive error. Indeed, we show that for estimating the size of the maximum matching or k-core number of a vertex, allowing small multiplicative approximations is what brings the additive error down to polylogarithmic. We complement these results with improved upper bounds on the additive error when no multiplicative approximation is allowed.
Beyond graphs, our techniques also show that polynomial additive error is unavoidable for the Simultaneous Norm Estimation problem in the insertions-only setting. When multiplicative approximations are allowed, we circumvent this lower bound by giving the first continual mechanism with polylogarithmic additive error under (1 + ζ) multiplicative approximations, for any ζ > 0, for estimating all monotone symmetric norms simultaneously.
In the item-level setting, we show polynomial lower bounds on the product of the multiplicative and the additive error of continual mechanisms for a large range of graph problems. To the best of our knowledge, these are the first lower bounds shown for any differentially private mechanism under continual release with multiplicative error. To obtain these results, we prove a new lower bound on the product of multiplicative and additive error for the 1-Way-Marginals problem, and give reductions from 1-Way-Marginals to our desired graph problems. This generalizes the prior results of Hardt and Talwar [STOC 2010] and Bun, Ullman and Vadhan [STOC 2014, SIAM J. Comput. 2018], who gave lower bounds on the additive error for the special case of mechanisms with no multiplicative error.},
  author       = {Aryanfard, Bardiya and Henzinger, Monika H and Saulpic, David and Sricharan, A. R.},
  issn         = {2836-6573},
  journal      = {Proceedings of the ACM on Management of Data},
  number       = {2},
  pages        = {1--27},
  publisher    = {Association for Computing Machinery},
  title        = {{Improved lower bounds for privacy under continual release}},
  doi          = {10.1145/3801903},
  volume       = {4},
  year         = {2026},
}