---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22322'
abstract:
- lang: eng
  text: "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.\r\nBeyond 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.\r\nIn 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."
acknowledgement: "Bardiya Aryanfard and Monika Henzinger were supported by the European
  Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
  programme (Grant agreement\r\nNo. 101019564). For open access purposes, the author
  has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript
  version arising from this submission. Funded by the\r\nEuropean union. Views and
  opinions expressed are however those of the author(s) only and do\r\nnot necessarily
  reflect those of the European Union or the European Research Council Executive\r\nAgency.
  Neither the European Union nor the granting authority can be held responsible for
  them"
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Bardiya
  full_name: Aryanfard, Bardiya
  id: 1e8f4084-31df-11ee-b195-f706b4b77091
  last_name: Aryanfard
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: David
  full_name: Saulpic, David
  id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
  last_name: Saulpic
- first_name: A. R.
  full_name: Sricharan, A. R.
  last_name: Sricharan
citation:
  ama: Aryanfard B, Henzinger M, Saulpic D, Sricharan AR. Improved lower bounds for
    privacy under continual release. <i>Proceedings of the ACM on Management of Data</i>.
    2026;4(2):1-27. doi:<a href="https://doi.org/10.1145/3801903">10.1145/3801903</a>
  apa: Aryanfard, B., Henzinger, M., Saulpic, D., &#38; Sricharan, A. R. (2026). Improved
    lower bounds for privacy under continual release. <i>Proceedings of the ACM on
    Management of Data</i>. Association for Computing Machinery. <a href="https://doi.org/10.1145/3801903">https://doi.org/10.1145/3801903</a>
  chicago: Aryanfard, Bardiya, Monika Henzinger, David Saulpic, and A. R. Sricharan.
    “Improved Lower Bounds for Privacy under Continual Release.” <i>Proceedings of
    the ACM on Management of Data</i>. Association for Computing Machinery, 2026.
    <a href="https://doi.org/10.1145/3801903">https://doi.org/10.1145/3801903</a>.
  ieee: B. Aryanfard, M. Henzinger, D. Saulpic, and A. R. Sricharan, “Improved lower
    bounds for privacy under continual release,” <i>Proceedings of the ACM on Management
    of Data</i>, vol. 4, no. 2. Association for Computing Machinery, pp. 1–27, 2026.
  ista: Aryanfard B, Henzinger M, Saulpic D, Sricharan AR. 2026. Improved lower bounds
    for privacy under continual release. Proceedings of the ACM on Management of Data.
    4(2), 1–27.
  mla: Aryanfard, Bardiya, et al. “Improved Lower Bounds for Privacy under Continual
    Release.” <i>Proceedings of the ACM on Management of Data</i>, vol. 4, no. 2,
    Association for Computing Machinery, 2026, pp. 1–27, doi:<a href="https://doi.org/10.1145/3801903">10.1145/3801903</a>.
  short: B. Aryanfard, M. Henzinger, D. Saulpic, A.R. Sricharan, Proceedings of the
    ACM on Management of Data 4 (2026) 1–27.
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-14T05:33:58Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-07-16T09:30:31Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1145/3801903
ec_funded: 1
external_id:
  arxiv:
  - '2512.15981'
file:
- access_level: open_access
  checksum: 21a48a620e415a31a3874077c55bc6c3
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-16T09:29:08Z
  date_updated: 2026-07-16T09:29:08Z
  file_id: '22349'
  file_name: 2026_ACMMgmtData_Aryanfard.pdf
  file_size: 934963
  relation: main_file
  success: 1
file_date_updated: 2026-07-16T09:29:08Z
has_accepted_license: '1'
intvolume: '         4'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1-27
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
publication: Proceedings of the ACM on Management of Data
publication_identifier:
  issn:
  - 2836-6573
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Improved lower bounds for privacy under continual release
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2026'
...