--- OA_place: publisher OA_type: gold PlanS_conform: '1' _id: '22318' abstract: - lang: eng text: "Many intended uses of differential privacy involve a continual mechanism that is set up to run continuously\r\nover a long period of time, making more statistical releases as either queries come in or the dataset is updated.\r\nIn this paper, we give the first general treatment of privacy against adaptive adversaries for mechanisms that\r\nsupport dataset updates and a variety of queries, all arbitrarily interleaved. It also models a very general notion\r\nof neighboring, that includes both event-level and user-level privacy. We prove several concurrent composition\r\ntheorems for continual mechanisms, which ensure privacy even when an adversary can interleave its queries\r\nand dataset updates to the different composed mechanisms. Previous concurrent composition theorems for\r\ndifferential privacy were only for the case when the dataset is static, with no adaptive updates. We also give\r\nthe first interactive and continual generalizations of the “parallel composition theorem” for noninteractive\r\ndifferential privacy. Specifically, we show that the analogue of the noninteractive parallel composition theorem\r\nholds if either there are no adaptive dataset updates or each of the composed mechanisms satisfies pure\r\ndifferential privacy, but it fails to hold for composing approximately differentially private mechanisms with\r\ndataset updates. Thus, we prove a tight new composition theorem for this case. In addition, we prove concurrent\r\nfilter compositions theorems for the scenarios in which the privacy parameters are adaptively chosen. We\r\nextend these results to other measures of differential privacy, including Rényi DP and \U0001D453 -DP.\r\nWe 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\r\ntheorems on the sub-mechanisms, without further privacy loss. This enables us to give a simpler and modular\r\nprivacy analysis of a recent continual histogram mechanism of Henzinger, Sricharan, and Steiner. In the\r\ncase of approximate DP, ours is the first proof that shows that its privacy holds against adaptive adversaries.\r\nWe also provide a framework that simplifies the analysis of local differential privacy when the protocol\r\nincludes multi-round server-user interactions. Using this result, we simplify the privacy analysis of the core\r\ndecomposition protocol of Dhulipala, Henzinger, Li, Liu, Sricharan, and Zhu [5]." acknowledgement: "1Salil Vadhan was supported by NSF grant BCS-2218803, a grant from the Sloan Foundation, and\r\na Simons Investigator Award. Work began while a Visiting Researcher at the Bocconi University\r\nDepartment of Computing Sciences, supported by Luca Trevisan’s ERC Project GA-834861.\r\n2Monika Henzinger and Roodabeh Safavi 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), and the Austrian Science Fund (FWF) under grants DOI 10.55776/Z422, DOI\r\n10.55776/I5982, and DOI 10.55776/P33775. For open access purposes, the author has applied a CC BY\r\npublic copyright license to any author-accepted manuscript version arising from this submission.\r\nViews and opinions expressed are however those of the author(s)\r\nonly and do not necessarily reflect those of the European Union\r\nor the European Research Council Executive Agency. Neither the\r\nEuropean Union nor the granting authority can be held responsible for them." article_processing_charge: Yes article_type: original arxiv: 1 author: - 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: Roodabeh full_name: Safavi Hemami, Roodabeh id: 72ed2640-8972-11ed-ae7b-f9c81ec75154 last_name: Safavi Hemami - first_name: Salil full_name: Vadhan, Salil last_name: Vadhan citation: ama: Henzinger M, Safavi Hemami R, Vadhan S. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 2026;4(2):1-26. doi:10.1145/3801895 apa: Henzinger, M., Safavi Hemami, R., & Vadhan, S. (2026). Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801895 chicago: Henzinger, Monika, Roodabeh Safavi Hemami, and Salil Vadhan. “Concurrent Composition for Differentially Private Continual Mechanisms.” Proceedings of the ACM on Management of Data. Association for Computing Machinery, 2026. https://doi.org/10.1145/3801895. ieee: M. Henzinger, R. Safavi Hemami, and S. Vadhan, “Concurrent composition for differentially private continual mechanisms,” Proceedings of the ACM on Management of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–26, 2026. ista: Henzinger M, Safavi Hemami R, Vadhan S. 2026. Concurrent composition for differentially private continual mechanisms. Proceedings of the ACM on Management of Data. 4(2), 1–26. mla: Henzinger, Monika, et al. “Concurrent Composition for Differentially Private Continual Mechanisms.” Proceedings of the ACM on Management of Data, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–26, doi:10.1145/3801895. short: M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26. corr_author: '1' das_tickbox: '0' date_created: 2026-07-13T14:59:14Z date_published: 2026-06-01T00:00:00Z date_updated: 2026-07-16T09:14:49Z day: '01' ddc: - '000' department: - _id: MoHe doi: 10.1145/3801895 ec_funded: 1 external_id: arxiv: - '2411.03299' file: - access_level: open_access checksum: c6c5e256d02b90682c0690c3bee94040 content_type: application/pdf creator: dernst date_created: 2026-07-16T09:09:53Z date_updated: 2026-07-16T09:09:53Z file_id: '22345' file_name: 2026_ACMMgmtData_Henzinger.pdf file_size: 655405 relation: main_file success: 1 file_date_updated: 2026-07-16T09:09:53Z has_accepted_license: '1' intvolume: ' 4' issue: '2' keyword: - differential privacy - concurrent composition - continual release - continual observation - data streaming - continual mechanisms - concurrent parallel composition - concurrent filter composition language: - iso: eng month: '06' oa: 1 oa_version: Published Version page: 1-26 project: - _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62 call_identifier: H2020 grant_number: '101019564' name: The design and evaluation of modern fully dynamic data structures - _id: bda196b2-d553-11ed-ba76-8e8ee6c21103 grant_number: I05982 name: Static and Dynamic Hierarchical Graph Decompositions - _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe grant_number: P33775 name: Fast Algorithms for a Reactive Network Layer - _id: 34def286-11ca-11ed-8bc3-da5948e1613c grant_number: Z00422 name: Efficient algorithms 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: Concurrent composition for differentially private continual mechanisms 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' ... --- 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. Proceedings of the ACM on Management of Data. 2026;4(2):1-27. doi:10.1145/3801903 apa: Aryanfard, B., Henzinger, M., Saulpic, D., & Sricharan, A. R. (2026). Improved lower bounds for privacy under continual release. Proceedings of the ACM on Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801903 chicago: Aryanfard, Bardiya, Monika Henzinger, David Saulpic, and A. R. Sricharan. “Improved Lower Bounds for Privacy under Continual Release.” Proceedings of the ACM on Management of Data. Association for Computing Machinery, 2026. https://doi.org/10.1145/3801903. ieee: B. Aryanfard, M. Henzinger, D. Saulpic, and A. R. Sricharan, “Improved lower bounds for privacy under continual release,” Proceedings of the ACM on Management of Data, 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.” Proceedings of the ACM on Management of Data, vol. 4, no. 2, Association for Computing Machinery, 2026, pp. 1–27, doi:10.1145/3801903. 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' ...