---
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
fulldoi: https://doi.org/10.1145/3801895
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: '22716'
abstract:
- lang: eng
text: We give an algorithm that, with high probability, maintains a (1-ε)-approximate
s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge
insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow
on the final graph. This is the first algorithm to achieve polylogarithmic amortized
update time for dense graphs (m = Ω(n²)), and more generally, for graphs where
F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph
sparsification technique of Karger and Levine [SICOMP '15], originally designed
for computing exact maximum flows in the static setting. Our main contributions
are (i) showing how to maintain such sparsifiers for approximate maximum flows
in the incremental setting and (ii) generalizing the cut sparsification framework
of Fung et al. [SICOMP '19] from undirected graphs to balanced directed graphs.
acknowledgement: "M. Henzinger: This project has received funding from the European
Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation
programme (MoDynStruct, No. 101019564) and the Austrian Science Fund\r\n(FWF)
grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
with additional funding from the\r\nnetidee SCIENCE Stiftung, 2020–2024. Views and
opinions expressed are those of the author(s) only and do not necessarily\r\nreflect
those of the European Union or the European Research Council Executive Agency. Neither
the European Union nor\r\nthe granting authority can be held responsible for them"
article_number: '31'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
citation:
ama: Goranci G, Henzinger M, Räcke H, Sricharan AR. Incremental approximate maximum
flow via residual graph sparsification. ACM Transactions on Algorithms.
2026;22(3). doi:10.1145/3816252
apa: Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. R. (2026). Incremental
approximate maximum flow via residual graph sparsification. ACM Transactions
on Algorithms. ACM. https://doi.org/10.1145/3816252
chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. R. Sricharan. “Incremental
Approximate Maximum Flow via Residual Graph Sparsification.” ACM Transactions
on Algorithms. ACM, 2026. https://doi.org/10.1145/3816252.
ieee: G. Goranci, M. Henzinger, H. Räcke, and A. R. Sricharan, “Incremental approximate
maximum flow via residual graph sparsification,” ACM Transactions on Algorithms,
vol. 22, no. 3. ACM, 2026.
ista: Goranci G, Henzinger M, Räcke H, Sricharan AR. 2026. Incremental approximate
maximum flow via residual graph sparsification. ACM Transactions on Algorithms.
22(3), 31.
mla: Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual
Graph Sparsification.” ACM Transactions on Algorithms, vol. 22, no. 3,
31, ACM, 2026, doi:10.1145/3816252.
short: G. Goranci, M. Henzinger, H. Räcke, A.R. Sricharan, ACM Transactions on Algorithms
22 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-08-16T22:01:43Z
date_published: 2026-07-06T00:00:00Z
date_updated: 2026-08-20T06:28:01Z
day: '06'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3816252
ec_funded: 1
external_id:
arxiv:
- '2502.09105'
file:
- access_level: open_access
checksum: 97969d26dab25c3a35be3ae4dd0fd9ee
content_type: application/pdf
creator: dernst
date_created: 2026-08-20T06:19:51Z
date_updated: 2026-08-20T06:19:51Z
file_id: '22740'
file_name: 2026_TransactionsAlgorithms_Goranci.pdf
file_size: 2272512
relation: main_file
success: 1
file_date_updated: 2026-08-20T06:19:51Z
fulldoi: https://doi.org/10.1145/3816252
has_accepted_license: '1'
intvolume: ' 22'
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: ACM Transactions on Algorithms
publication_identifier:
eissn:
- 1549-6333
issn:
- 1549-6325
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
record:
- id: '21280'
relation: earlier_version
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Incremental approximate maximum flow via residual graph sparsification
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: 22
year: '2026'
...
---
OA_place: publisher
_id: '22281'
abstract:
- lang: eng
text: "In this thesis, we took a look at networks, and more specifically, at networks
that change over time, whether those are networks in the distributed algorithms
sense of the word, or the graph algorithm sense. \r\n\r\nIn distributed algorithms,
we looked at two main problems. First, the broadcast problem: given n agents,
each agent is tasked to forward a (unique) message to every other agent. Agents
collaborate and can copy and forward all messages they have received up until
that point. Broadcast is achieved when one agent has successfully broadcast its
message to everyone else. We studied the case where the communication network
is controlled by an adversary, under the condition that the graph is rooted in
every round of communication. We show that the adversary can delay broadcast for
at most l\r\n(1 + √\r\n2)n\r\nm\r\n rounds, improving on the $O(n\\log\\log n)$
previous upper bound~\\cite{fugger2020radius}, and asymptotically matching the
$\\sim 1.5n$ lower bound~\\cite{schwarz2017linear}.\r\n\r\nWe then looked at the
stochastic version of the problem: here, the adversary -- parametrized by $k$
where $k=0$ signifies that the adversary has no control, and $k=n$ that the adversary
has full control -- can choose parts of the graph, and the graph is then completed
stochastically. Here, we are able to look at a stronger version of broadcast:
instead of having $n$ messages trying to be broadcast in parallel, we can assume
that only one message needs to be broadcasted. We show the bound $\\Theta(k+\\log
n)$.\r\n\r\nThen, we looked at undecided states dynamics in population protocols:
given a population of $n$ agents, where each initially holds an opinion among
$k$ different ones. In each round, two agents are chosen uniformly at random,
and can interact. If they have different opinions, they forget their opinions
and become undecided. If one of them is undecided while the other has an opinion,
they undecided agent copies they opinion of the decided one. The question is then,
how many interactions does it take for the whole population to share the same
opinion? We show a $\\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})$ lower bound
\ for any $k = o\\left(\\frac {\\sqrt n}{\\log n}\\right)$.\r\nThis is tight for
any $ k \\le n^{\\frac 1 2 - \\epsilon}$, where $\\epsilon >0$ can be any small
constant, matching the known $O(kn\\log n)$ upper bound for $k = O\\left(\\frac
{\\sqrt n} {\\log ^2 n}\\right)$~\\cite{DBLP:conf/podc/AmirABBHKL23}.\r\n\r\nFinally,
in dynamic algorithms, we study the minimum cut problem: we are given a graph,
whose vertex set we want to partition into two subsets such that the number of
edges crossing from one subset to the other is minimized. Then, the graph can
be updated via edge insertions or deletions, and we must update the solution without
recomputing everything from scratch. We present an exact fully-dynamic minimum
cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum
cut size is at most $2^{\\Theta(\\log^{3/4-c}n)}$ for any $c>0$, improving on
the previous algorithm~\\cite{DBLP:conf/soda/JinST24} whose minimum cut size limit
is $(\\log n)^{o(1)}$. Using sparsification and randomization techniques, we are
able to extend this to all values of the minimum cut in weighted graphs, at the
cost of a $(1+o(1))$-approximation ratio."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564)\r\n\"The Design and Evaluation of Modern Fully Dynamic
Data Structures\" , from the\r\nAustrian Science Fund (FWF) grant DOI 10.55776/I5982
\"Static and Dynamic Hierarchical\r\nGraph Decompositions\", and from the Austrian
Science Fund (FWF) and netIDEE SCIENCE\r\nproject P 33775-N, \"Fast Algorithms for
a Reactive Network Layer\".\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
citation:
ama: 'El-Hayek A. Handling updates and failures: Dynamic graph algorithms and distributed
computing on dynamic networks. 2026. doi:10.15479/AT-ISTA-22281'
apa: 'El-Hayek, A. (2026). Handling updates and failures: Dynamic graph algorithms
and distributed computing on dynamic networks. Institute of Science and Technology
Austria. https://doi.org/10.15479/AT-ISTA-22281'
chicago: 'El-Hayek, Antoine. “Handling Updates and Failures: Dynamic Graph Algorithms
and Distributed Computing on Dynamic Networks.” Institute of Science and Technology
Austria, 2026. https://doi.org/10.15479/AT-ISTA-22281.'
ieee: 'A. El-Hayek, “Handling updates and failures: Dynamic graph algorithms and
distributed computing on dynamic networks,” Institute of Science and Technology
Austria, 2026.'
ista: 'El-Hayek A. 2026. Handling updates and failures: Dynamic graph algorithms
and distributed computing on dynamic networks. Institute of Science and Technology
Austria.'
mla: 'El-Hayek, Antoine. Handling Updates and Failures: Dynamic Graph Algorithms
and Distributed Computing on Dynamic Networks. Institute of Science and Technology
Austria, 2026, doi:10.15479/AT-ISTA-22281.'
short: 'A. El-Hayek, Handling Updates and Failures: Dynamic Graph Algorithms and
Distributed Computing on Dynamic Networks, Institute of Science and Technology
Austria, 2026.'
corr_author: '1'
date_created: 2026-07-13T09:39:59Z
date_published: 2026-07-13T00:00:00Z
date_updated: 2026-10-21T08:05:35Z
day: '13'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: MoHe
doi: 10.15479/AT-ISTA-22281
doi_confirm: '1'
ec_funded: 1
file:
- access_level: open_access
checksum: 923e4ca769c9ef2f6b0b005444faf462
content_type: application/pdf
creator: aelhayek
date_created: 2026-07-17T11:39:47Z
date_updated: 2026-07-17T11:39:47Z
file_id: '22356'
file_name: 2026_El-Hayek_Antoine_Thesis.pdf
file_size: 5465973
relation: main_file
success: 1
- access_level: closed
checksum: 262689f9df27dd6c2c7c7861f1de7329
content_type: application/x-zip-compressed
creator: aelhayek
date_created: 2026-07-17T11:40:34Z
date_updated: 2026-07-20T11:29:38Z
file_id: '22357'
file_name: 2026_El-Hayek_Antoine_Thesis.zip
file_size: 9116107
relation: source_file
file_date_updated: 2026-07-20T11:29:38Z
fulldoi: https://doi.org/10.15479/AT-ISTA-22281
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '244'
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
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publisher_comment: Sections 2.4 and 7.1 and chapter 6 are not CC-BY 4.0, they are
All Rights Reserved.
related_material:
record:
- id: '20051'
relation: part_of_dissertation
status: public
- id: '19982'
relation: part_of_dissertation
status: public
- id: '21720'
relation: part_of_dissertation
status: public
- id: '22374'
relation: part_of_dissertation
status: public
- id: '22373'
relation: part_of_dissertation
status: public
- id: '18557'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
title: 'Handling updates and failures: Dynamic graph algorithms and distributed computing
on dynamic networks'
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: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '19038'
abstract:
- lang: eng
text: Differentially private weighted prefix sum under continual observation is
a crucial component in the production-level deployment of private next-word prediction
for Gboard, which, according to Google, has over a billion users. More specifically,
Google uses a differentially private mechanism to sum weighted gradients in its
private follow-the-regularized leader algorithm. Apart from efficiency, the additive
error of the private mechanism is crucial as multiplied with the square root of
the model’s dimension d (with d ranging up to 10 trillion, for example, Switch
Transformers or M6-10T), it determines the accuracy of the learning system. So,
any improvement in leading constant matters significantly in practice. In this
paper, we show a novel connection between mechanisms for continual weighted prefix
sum and a concept in representation theory known as the group matrix introduced
in correspondence between Dedekind and Frobenius (Sitzungsber. Preuss. Akad. Wiss.
Berlin, 1897) and generalized by Schur (Journal für die reine und angewandte Mathematik,
1904). To the best of our knowledge, this is the first application of group algebra
in the analysis of differentially private algorithms. Using this connection, we
analyze a class of matrix norms known as factorization norms that give upper and
lower bounds for the additive error under general ℓp-norms of the matrix mechanism.
This allows us to give 1. the first efficient factorization that matches the best-known
non-constructive upper bound on the factorization norm by Mathias (SIAM Journal
of Matrix Analysis and Applications, 1993) for the matrix used in Google’s deployment,
and also improves on the previous best-known constructive bound of Fichtenberger,
Henzinger, and Upadhyay (ICML 2023) and Henzinger, Upadhyay, and Upadhyay (SODA
2023); thereby, partially resolving an open question in operator theory, 2. the
first upper bound on the additive error for a large class of weight functions
for weighted prefix sum problems, including the sliding window matrix (Bolot,
Fawaz, Muthukrishnan, Nikolov, and Taft (ICDT 2013). We also improve the bound
on factorizing the striped matrix used for outputting a synthetic graph that approximates
all cuts (Fichtenberger, Henzinger, and Upadhyay (ICML 2023)); 3. a general improved
upper bound on the factorization norms that depend on algebraic properties of
the weighted sum matrices and that applies to a more general class of weighting
functions than the ones considered in Henzinger, Upadhyay, and Upadhyay (SODA
2024). Using the known connection between these factorization norms and the ℓp-error
of continual weighted sum, we give an upper bound on the ℓp-error for the continual
weighted sum problem for p ≥ 2.
acknowledgement: 'Monika Henzinger: This project has received funding from the European
Research Council(ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grantagreement No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422,grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional
funding from the netidee SCIENCEStiftung, 2020–2024.Jalaj Upadhyay’s research was
funded by the Rutgers Decanal Grant no. 302918 and an unrestricted giftfrom Google.
This work was done in part while visiting the Institute of Science and Technology
Austria (ISTA).The authors would like to thank Sarvagya Upadhyay for the initial
discussion and feedback on the early draft of the paper. The authors would like
to thank the anonymous reviewers, Brendan McMahan and Abhradeep Thakurta for the
discussions that helped improve the presentation of the final version of the paper.'
article_processing_charge: No
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: Jalaj
full_name: Upadhyay, Jalaj
last_name: Upadhyay
citation:
ama: 'Henzinger M, Upadhyay J. Improved differentially private continual observation
using group algebra. In: Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms. Vol 5. Association for Computing Machinery; 2025:2951-2970.
doi:10.1137/1.9781611978322.95'
apa: 'Henzinger, M., & Upadhyay, J. (2025). Improved differentially private
continual observation using group algebra. In Proceedings of the 2025 Annual
ACM-SIAM Symposium on Discrete Algorithms (Vol. 5, pp. 2951–2970). New Orleans,
LA, United States: Association for Computing Machinery. https://doi.org/10.1137/1.9781611978322.95'
chicago: Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private
Continual Observation Using Group Algebra.” In Proceedings of the 2025 Annual
ACM-SIAM Symposium on Discrete Algorithms, 5:2951–70. Association for Computing
Machinery, 2025. https://doi.org/10.1137/1.9781611978322.95.
ieee: M. Henzinger and J. Upadhyay, “Improved differentially private continual observation
using group algebra,” in Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms, New Orleans, LA, United States, 2025, vol. 5, pp.
2951–2970.
ista: 'Henzinger M, Upadhyay J. 2025. Improved differentially private continual
observation using group algebra. Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 5, 2951–2970.'
mla: Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual
Observation Using Group Algebra.” Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms, vol. 5, Association for Computing Machinery, 2025,
pp. 2951–70, doi:10.1137/1.9781611978322.95.
short: M. Henzinger, J. Upadhyay, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms, Association for Computing Machinery, 2025, pp. 2951–2970.
conference:
end_date: 2025-01-15
location: New Orleans, LA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2025-01-12
date_created: 2025-02-17T09:31:03Z
date_published: 2025-01-20T00:00:00Z
date_updated: 2025-04-14T13:50:49Z
day: '20'
department:
- _id: MoHe
doi: 10.1137/1.9781611978322.95
ec_funded: 1
external_id:
arxiv:
- '2412.02840'
fulldoi: https://doi.org/10.1137/1.9781611978322.95
intvolume: ' 5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.02840
month: '01'
oa: 1
oa_version: Preprint
page: 2951 - 2970
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- 979-833131200-8
issn:
- 1071-9040
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved differentially private continual observation using group algebra
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 5
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '19858'
abstract:
- lang: eng
text: "Given a graph G that undergoes a sequence of edge insertions and deletions,
we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different
colors, color as many edges of G as possible such that no two adjacent edges share
the same color. While this problem is different from simply maintaining a b-matching
with b = k, the two problems are related. However, maximum b-matching can be solved
efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for
k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a
new integrality gap result and we adapt Wajc’s matching sparsification scheme
[David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis,
we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm
builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and
Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation
in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA
algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya,
Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching
and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update
time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching
algorithm as a black box, so any future improvement in the approximation ratio
for dynamic b-matching will automatically translate into a better approximation
ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update
time, which guarantees a 2.16 approximation factor."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the\r\nEuropean Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422,
grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding
from the netidee SCIENCE Stiftung, 2020–2024. This work was further supported by
the Federal Ministry of Education and Research (BMBF) project, 6G-RIC: 6G Research
and Innovation Cluster, grant 16KISK020K."
alternative_title:
- LIPIcs
article_number: '4'
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- first_name: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum
k-edge coloring. In: 4th Symposium on Algorithmic Foundations of Dynamic Networks.
Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SAND.2025.4'
apa: 'El-Hayek, A., Hanauer, K., & Henzinger, M. (2025). On b-matching and fully-dynamic
maximum k-edge coloring. In 4th Symposium on Algorithmic Foundations of Dynamic
Networks (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2025.4'
chicago: El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching
and Fully-Dynamic Maximum k-Edge Coloring.” In 4th Symposium on Algorithmic
Foundations of Dynamic Networks, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SAND.2025.4.
ieee: A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic
maximum k-edge coloring,” in 4th Symposium on Algorithmic Foundations of Dynamic
Networks, Liverpool, United Kingdom, 2025, vol. 330.
ista: 'El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic
maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks.
SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330,
4.'
mla: El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.”
4th Symposium on Algorithmic Foundations of Dynamic Networks, vol. 330,
4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SAND.2025.4.
short: A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic
Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-06-11
location: Liverpool, United Kingdom
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2025-06-09
corr_author: '1'
date_created: 2025-06-22T22:02:06Z
date_published: 2025-06-02T00:00:00Z
date_updated: 2025-09-30T13:37:28Z
day: '02'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.SAND.2025.4
ec_funded: 1
external_id:
arxiv:
- '2310.01149'
isi:
- '001532136900004'
file:
- access_level: open_access
checksum: ad93a1e052adb29d7bfe8bd551bab193
content_type: application/pdf
creator: dernst
date_created: 2025-06-23T11:23:29Z
date_updated: 2025-06-23T11:23:29Z
file_id: '19872'
file_name: 2025_LIPIcs_ElHayek.pdf
file_size: 995666
relation: main_file
success: 1
file_date_updated: 2025-06-23T11:23:29Z
fulldoi: https://doi.org/10.4230/LIPIcs.SAND.2025.4
has_accepted_license: '1'
intvolume: ' 330'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: 4th Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
isbn:
- '9783959773683'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: On b-matching and fully-dynamic maximum k-edge coloring
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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 330
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20052'
abstract:
- lang: eng
text: "This paper revisits a fundamental distributed computing problem in the population
protocol model. Provided n agents each starting with an input color in [k], the
relative majority problem asks to find the predominant color. In the population
protocol model, at each time step, a scheduler selects two agents that first learn
each other's states and then update their states based on what they learned.\r\nWe
present the Circles protocol that solves the relative majority problem with k3
states. It is always-correct under weakly fair scheduling. Not only does it improve
upon the best known upper bound of O(k7), but it also shows a strikingly simpler
design inspired by energy minimization in chemical settings."
acknowledgement: 'This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/I5982,
and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung,
2020–2024 and the German Research Foundation (DFG), grant 470029389 (FlexNets). '
article_processing_charge: No
author:
- first_name: Tom-Lukas
full_name: Breitkopf, Tom-Lukas
last_name: Breitkopf
- first_name: Julien
full_name: Dallot, Julien
last_name: Dallot
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Brief announcement: Minimizing
energy solves relative majority with a cubic number of states in population protocols.
In: Proceedings of the ACM Symposium on Principles of Distributed Computing.
Association for Computing Machinery; 2025:549-552. doi:10.1145/3732772.3733512'
apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2025). Brief
announcement: Minimizing energy solves relative majority with a cubic number of
states in population protocols. In Proceedings of the ACM Symposium on Principles
of Distributed Computing (pp. 549–552). Huatulco, Mexico: Association for
Computing Machinery. https://doi.org/10.1145/3732772.3733512'
chicago: 'Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid.
“Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number
of States in Population Protocols.” In Proceedings of the ACM Symposium on
Principles of Distributed Computing, 549–52. Association for Computing Machinery,
2025. https://doi.org/10.1145/3732772.3733512.'
ieee: 'T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Brief announcement:
Minimizing energy solves relative majority with a cubic number of states in population
protocols,” in Proceedings of the ACM Symposium on Principles of Distributed
Computing, Huatulco, Mexico, 2025, pp. 549–552.'
ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2025. Brief announcement:
Minimizing energy solves relative majority with a cubic number of states in population
protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing.
PODC: Symposium on Principles of Distributed Computing, 549–552.'
mla: 'Breitkopf, Tom-Lukas, et al. “Brief Announcement: Minimizing Energy Solves
Relative Majority with a Cubic Number of States in Population Protocols.” Proceedings
of the ACM Symposium on Principles of Distributed Computing, Association for
Computing Machinery, 2025, pp. 549–52, doi:10.1145/3732772.3733512.'
short: T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the
ACM Symposium on Principles of Distributed Computing, Association for Computing
Machinery, 2025, pp. 549–552.
conference:
end_date: 2025-06-20
location: Huatulco, Mexico
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2025-06-16
corr_author: '1'
date_created: 2025-07-21T08:17:04Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2026-02-16T11:46:37Z
day: '13'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3732772.3733512
ec_funded: 1
external_id:
isi:
- '001525534800069'
file:
- access_level: open_access
checksum: e99679ffb28877b7cea4d54860302790
content_type: application/pdf
creator: dernst
date_created: 2025-08-05T07:32:01Z
date_updated: 2025-08-05T07:32:01Z
file_id: '20123'
file_name: 2025_PODC_Breitkopf.pdf
file_size: 549706
relation: main_file
success: 1
file_date_updated: 2025-08-05T07:32:01Z
fulldoi: https://doi.org/10.1145/3732772.3733512
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 549-552
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
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9798400718854'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: 'Brief announcement: Minimizing energy solves relative majority with a cubic
number of states in population protocols'
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20301'
abstract:
- lang: eng
text: "We study privately releasing column sums of a d-dimensional table with entries
from a universe χ undergoing T row updates, called histogram under continual release.
Our mechanisms give better additive ℓ∞-error than existing mechanisms for a large
class of queries and input streams. Our first contribution is an output-sensitive
mechanism in the insertions-only model (χ = {0, 1}) for maintaining (i) the histogram
or (ii) queries that do not require maintaining the entire histogram, such as
the maximum or minimum column sum, the median, or any quantiles. The mechanism
has an additive error of O(d log2 (dq∗) + log T) whp, where q∗ is the maximum
output value over all time steps on this dataset. The mechanism does not require
q∗ as input. This breaks the Ω(d log T) bound of prior work when q∗ ≪ T. Our second
contribution is a mechanism for the turnstile model that admits negative entry
updates (χ = {−1, 0, 1}). This mechanism has an additive error of O(d log2(dK)
+ log T) whp, where K is the number of times two consecutive data rows differ,
and the mechanism does not require K as input. This is useful when monitoring
inputs that only vary under unusual circumstances. For d = 1 this gives the first\r\nprivate
mechanism with error O(log2 K + log T) for continual counting in the turnstile
model, improving on the O(log2 n + log T) error bound by Dwork et al. (2015),
where n is the number of ones in the stream, as well as allowing negative entries,
while Dwork et al. (2015) can only handle nonnegative entries (χ = {0, 1}). "
acknowledgement: "MH: This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422,
grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding
from the netidee SCIENCE Stiftung, 2020–2024. TAS: This work was supported by a
research grant (VIL51463)\r\nfrom VILLUM FONDEN."
alternative_title:
- PMLR
article_processing_charge: No
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: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
- first_name: Teresa Anna
full_name: Steiner, Teresa Anna
last_name: Steiner
citation:
ama: 'Henzinger M, Sricharan AR, Steiner TA. Differentially private continual release
of histograms and related queries. In: The 28th International Conference on
Artificial Intelligence and Statistics. Vol 258. ML Research Press; 2025:1990-1998.'
apa: 'Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2025). Differentially
private continual release of histograms and related queries. In The 28th International
Conference on Artificial Intelligence and Statistics (Vol. 258, pp. 1990–1998).
Mai Khao, Thailand: ML Research Press.'
chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Differentially
Private Continual Release of Histograms and Related Queries.” In The 28th International
Conference on Artificial Intelligence and Statistics, 258:1990–98. ML Research
Press, 2025.
ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Differentially private
continual release of histograms and related queries,” in The 28th International
Conference on Artificial Intelligence and Statistics, Mai Khao, Thailand,
2025, vol. 258, pp. 1990–1998.
ista: 'Henzinger M, Sricharan AR, Steiner TA. 2025. Differentially private continual
release of histograms and related queries. The 28th International Conference on
Artificial Intelligence and Statistics. AISTATS: Conference on Artificial Intelligence
and Statistics, PMLR, vol. 258, 1990–1998.'
mla: Henzinger, Monika, et al. “Differentially Private Continual Release of Histograms
and Related Queries.” The 28th International Conference on Artificial Intelligence
and Statistics, vol. 258, ML Research Press, 2025, pp. 1990–98.
short: M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, The 28th International Conference
on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 1990–1998.
conference:
end_date: 2025-05-05
location: Mai Khao, Thailand
name: 'AISTATS: Conference on Artificial Intelligence and Statistics'
start_date: 2025-05-03
date_created: 2025-09-07T22:01:35Z
date_published: 2025-05-01T00:00:00Z
date_updated: 2025-09-09T07:09:22Z
day: '01'
department:
- _id: MoHe
ec_funded: 1
external_id:
arxiv:
- '2302.11341'
intvolume: ' 258'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2302.11341
month: '05'
oa: 1
oa_version: Preprint
page: 1990-1998
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: The 28th International Conference on Artificial Intelligence and Statistics
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Differentially private continual release of histograms and related queries
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 258
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20536'
abstract:
- lang: eng
text: "Uniquely represented (UR) data structures represent each logical state with
a unique storage state. We study the problem of maintaining a dynamic set of n
keys from a totally ordered universe in this context. UR structures are also called
\"strongly history independent\" structures in the literature.\r\nWe introduce
a two-layer data structure called (α,ε)-Randomized Block Search Tree (RBST) that
is uniquely represented and suitable for external memory (EM). Though RBSTs naturally
generalize the well-known binary Treaps, several new ideas are needed to analyze
the expected search, update, and storage efficiency in terms of block-reads, block-writes,
and blocks stored. We prove that searches have O(ε^{-1} + log_α n) block-reads,
that dynamic updates perform O(ε^{-1} + log_α(n)/α) block-writes and O(ε^{-2}+(1+(ε^{-1}+log
n)/α)log_α n) block-reads, and that (α, ε)-RBSTs have an asymptotic load-factor
of at least (1-ε) for every ε ∈ (0,1/2].\r\nThus (α, ε)-RBSTs improve on the known,
uniquely represented B-Treap [Golovin; ICALP'09]. Compared with non-UR structures,
the RBST is also, to the best of our knowledge, the first external memory structure
that is storage-efficient and has a non-amortized, write-efficient update bound."
acknowledgement: "This work was supported under the Australian Research Council Discovery
Projects\r\nfunding scheme (project number DP180102870). This project has received
funding from the\r\nEuropean Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (Grant agreement No. 101019564) “The Design
of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the Austrian Science
Fund (FWF) project Z 422-N and project “Fast Algorithms for a Reactive Network Layer
(ReactNet)” P 33775-N, with additional funding from the netidee SCIENCE Stiftung,
2020–2024."
alternative_title:
- LIPIcs
article_number: '47'
article_processing_charge: No
arxiv: 1
author:
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Martin P.
full_name: Seybold, Martin P.
last_name: Seybold
citation:
ama: 'Safavi Hemami R, Seybold MP. B-Treaps revised: Write efficient randomized
block search trees with high load. In: 19th International Symposium on Algorithms
and Data Structures. Vol 349. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2025. doi:10.4230/LIPIcs.WADS.2025.47'
apa: 'Safavi Hemami, R., & Seybold, M. P. (2025). B-Treaps revised: Write efficient
randomized block search trees with high load. In 19th International Symposium
on Algorithms and Data Structures (Vol. 349). Toronto, Canada: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.WADS.2025.47'
chicago: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write
Efficient Randomized Block Search Trees with High Load.” In 19th International
Symposium on Algorithms and Data Structures, Vol. 349. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/LIPIcs.WADS.2025.47.'
ieee: 'R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized
block search trees with high load,” in 19th International Symposium on Algorithms
and Data Structures, Toronto, Canada, 2025, vol. 349.'
ista: 'Safavi Hemami R, Seybold MP. 2025. B-Treaps revised: Write efficient randomized
block search trees with high load. 19th International Symposium on Algorithms
and Data Structures. WADS: Algorithms and Data Structures Symposium, LIPIcs, vol.
349, 47.'
mla: 'Safavi Hemami, Roodabeh, and Martin P. Seybold. “B-Treaps Revised: Write Efficient
Randomized Block Search Trees with High Load.” 19th International Symposium
on Algorithms and Data Structures, vol. 349, 47, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, doi:10.4230/LIPIcs.WADS.2025.47.'
short: R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms
and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-08-15
location: Toronto, Canada
name: 'WADS: Algorithms and Data Structures Symposium'
start_date: 2025-08-11
corr_author: '1'
date_created: 2025-10-26T23:01:35Z
date_published: 2025-08-29T00:00:00Z
date_updated: 2025-10-27T07:10:49Z
day: '29'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.WADS.2025.47
ec_funded: 1
external_id:
arxiv:
- '2303.04722'
file:
- access_level: open_access
checksum: 196af33762831a78e87f4f95ecd8677b
content_type: application/pdf
creator: dernst
date_created: 2025-10-27T07:09:41Z
date_updated: 2025-10-27T07:09:41Z
file_id: '20540'
file_name: 2025_LIPIcs.WADS_Safavi.pdf
file_size: 1081870
relation: main_file
success: 1
file_date_updated: 2025-10-27T07:09:41Z
fulldoi: https://doi.org/10.4230/LIPIcs.WADS.2025.47
has_accepted_license: '1'
intvolume: ' 349'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: 19th International Symposium on Algorithms and Data Structures
publication_identifier:
isbn:
- '9783959773980'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'B-Treaps revised: Write efficient randomized block search trees with high
load'
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 349
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20051'
abstract:
- lang: eng
text: "We revisit the majority problem in the population protocol communication
model, as first studied by Angluin et al. (Distributed Computing 2008). We consider
a more general version of this problem known as plurality consensus, which has
already been studied intensively in the literature. In this problem, each node
in a system of n nodes, has initially one of k different opinions, and they need
to agree on the (relative) majority opinion. In particular, we consider the important
and intensively studied model of Undecided State Dynamics.\r\nOur main contribution
is an almost tight lower bound on the stabilization time: we prove that there
exists an initial configuration, even with bias \\Delta = \\omega(\\sqrt{n\\log
n}), where stabilization requires \\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})
interactions, or equivalently, \\Omega(k\\log \\frac {\\sqrt n} {k \\log n}) parallel
time for any k = o\\left(\\frac {\\sqrt n}{\\log n}\\right). This bound is tight
for any k \\le n^{\\frac 1 2 - \\epsilon}, where \\epsilon >0 can be any small
constant, as Amir et al.~(PODC'23) gave a O(k\\log n) parallel time upper bound
for k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right)."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/I5862,grant
DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with\r\nadditional funding from
the netidee SCIENCE Stiftung, 2020–2024\r\nand the German Research Foundation (DFG),
grant 470029389\r\n(FlexNets)."
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- first_name: Robert
full_name: Elsässer, Robert
last_name: Elsässer
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Elsässer R, Schmid S. An almost tight lower bound for plurality
consensus with undecided state dynamics in the population protocol model. In:
Proceedings of the ACM Symposium on Principles of Distributed Computing.
Association for Computing Machinery; 2025. doi:10.1145/3732772.3733505'
apa: 'El-Hayek, A., Elsässer, R., & Schmid, S. (2025). An almost tight lower
bound for plurality consensus with undecided state dynamics in the population
protocol model. In Proceedings of the ACM Symposium on Principles of Distributed
Computing. Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733505'
chicago: El-Hayek, Antoine, Robert Elsässer, and Stefan Schmid. “An Almost Tight
Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population
Protocol Model.” In Proceedings of the ACM Symposium on Principles of Distributed
Computing. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733505.
ieee: A. El-Hayek, R. Elsässer, and S. Schmid, “An almost tight lower bound for
plurality consensus with undecided state dynamics in the population protocol model,”
in Proceedings of the ACM Symposium on Principles of Distributed Computing,
Huatulco, Mexico, 2025.
ista: 'El-Hayek A, Elsässer R, Schmid S. 2025. An almost tight lower bound for plurality
consensus with undecided state dynamics in the population protocol model. Proceedings
of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on
Principles of Distributed Computing.'
mla: El-Hayek, Antoine, et al. “An Almost Tight Lower Bound for Plurality Consensus
with Undecided State Dynamics in the Population Protocol Model.” Proceedings
of the ACM Symposium on Principles of Distributed Computing, Association for
Computing Machinery, 2025, doi:10.1145/3732772.3733505.
short: A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery, 2025.
conference:
end_date: 2025-06-20
location: Huatulco, Mexico
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2025-06-16
corr_author: '1'
date_created: 2025-07-21T08:16:15Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2026-07-24T12:48:28Z
day: '13'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3732772.3733505
ec_funded: 1
external_id:
arxiv:
- '2505.02765'
isi:
- '001525534800066'
file:
- access_level: open_access
checksum: 52976d226f3f691aa519d71c1c718fa5
content_type: application/pdf
creator: dernst
date_created: 2025-08-04T09:10:55Z
date_updated: 2025-08-04T09:10:55Z
file_id: '20115'
file_name: 2025_PODC_ElHayek.pdf
file_size: 2200347
relation: main_file
success: 1
file_date_updated: 2025-08-04T09:10:55Z
fulldoi: https://doi.org/10.1145/3732772.3733505
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
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
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- ' 9798400718854'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
status: public
title: An almost tight lower bound for plurality consensus with undecided state dynamics
in the population protocol model
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19982'
abstract:
- lang: eng
text: "Dynamically maintaining the minimum cut in a graph G under edge insertions
and deletion is a fundamental problem in dynamic graph algorithms for which no
conditional lower bound on the time per operation exists. In an n-node graph the
best known (1 + o (1))-approximate algorithm takes update time [14]. If the minimum
cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n
o (1) update time exists [8].\r\nWe present the first fully dynamic algorithm
for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical
contribution is to show that it suffices to consider small-volume cuts in suitably
contracted graphs."
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’sHorizon 2020 research and innovation programme (MoDynStruct,
No. 101019564) and the Austrian Science Fund(FWF) grant DOI 10.55776/Z422, grant
DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the
netidee SCIENCE Stiftung, 2020–2024.
article_processing_charge: No
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- 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: Jason
full_name: Li, Jason
last_name: Li
citation:
ama: 'El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial
time per operation. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on
Discrete Algorithms. Society for Industrial and Applied Mathematics; 2025:750-784.
doi:10.1137/1.9781611978322.22'
apa: 'El-Hayek, A., Henzinger, M., & Li, J. (2025). Fully dynamic approximate
minimum cut in subpolynomial time per operation. In Proceedings of the 2025
Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 750–784). New Orleans,
LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978322.22'
chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate
Minimum Cut in Subpolynomial Time per Operation.” In Proceedings of the 2025
Annual ACM-SIAM Symposium on Discrete Algorithms, 750–84. Society for Industrial
and Applied Mathematics, 2025. https://doi.org/10.1137/1.9781611978322.22.
ieee: A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut
in subpolynomial time per operation,” in Proceedings of the 2025 Annual ACM-SIAM
Symposium on Discrete Algorithms, New Orleans, LA, United States, 2025, pp.
750–784.
ista: 'El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut
in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.'
mla: El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial
Time per Operation.” Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–84,
doi:10.1137/1.9781611978322.22.
short: A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the 2025 Annual ACM-SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
2025, pp. 750–784.
conference:
end_date: 2025-01-15
location: New Orleans, LA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2025-01-12
corr_author: '1'
date_created: 2025-07-10T13:08:57Z
date_published: 2025-01-07T00:00:00Z
date_updated: 2026-07-24T12:48:28Z
day: '07'
department:
- _id: MoHe
doi: 10.1137/1.9781611978322.22
ec_funded: 1
external_id:
arxiv:
- '2412.15069'
fulldoi: https://doi.org/10.1137/1.9781611978322.22
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.15069
month: '01'
oa: 1
oa_version: Preprint
page: 750-784
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611978322'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
status: public
title: Fully dynamic approximate minimum cut in subpolynomial time per operation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '21280'
abstract:
- lang: eng
text: We give an algorithm that, with high probability, maintains a (1-ε)-approximate
s-t maximum flow in undirected, uncapacitated n-vertex graphs undergoing m edge
insertions in Õ(m+ n F^*/ε) total update time, where F^{*} is the maximum flow
on the final graph. This is the first algorithm to achieve polylogarithmic amortized
update time for dense graphs (m = Ω(n²)), and more generally, for graphs where
F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph
sparsification technique of Karger and Levine [SICOMP '15], originally designed
for computing exact maximum flows in the static setting. Our main contributions
are (i) showing how to maintain such sparsifiers for approximate maximum flows
in the incremental setting and (ii) generalizing the cut sparsification framework
of Fung et al. [SICOMP '19] from undirected graphs to balanced directed graphs.
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation\r\nprogramme (MoDynStruct, No. 101019564) and the Austrian
Science Fund (FWF) grant DOI\r\n10.55776/Z422, grant DOI 10.55776/I5982, and grant
DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.
Harald Räcke: This project has received funding from the Deutsche Forschungsgemeinschaft
(DFG, German Research Foundation) – 498605858 and 470029389."
alternative_title:
- LIPIcs
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: A.
full_name: Sricharan, A.
last_name: Sricharan
citation:
ama: 'Goranci G, Henzinger M, Räcke H, Sricharan A. Incremental approximate maximum
flow via residual graph sparsification. In: 52nd International Colloquium on
Automata, Languages, and Programming. Vol 334. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2025:91:1-91:20. doi:10.4230/lipics.icalp.2025.91'
apa: 'Goranci, G., Henzinger, M., Räcke, H., & Sricharan, A. (2025). Incremental
approximate maximum flow via residual graph sparsification. In 52nd International
Colloquium on Automata, Languages, and Programming (Vol. 334, p. 91:1-91:20).
Aarhus, Denmark: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/lipics.icalp.2025.91'
chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. Sricharan. “Incremental
Approximate Maximum Flow via Residual Graph Sparsification.” In 52nd International
Colloquium on Automata, Languages, and Programming, 334:91:1-91:20. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2025. https://doi.org/10.4230/lipics.icalp.2025.91.
ieee: G. Goranci, M. Henzinger, H. Räcke, and A. Sricharan, “Incremental approximate
maximum flow via residual graph sparsification,” in 52nd International Colloquium
on Automata, Languages, and Programming, Aarhus, Denmark, 2025, vol. 334,
p. 91:1-91:20.
ista: 'Goranci G, Henzinger M, Räcke H, Sricharan A. 2025. Incremental approximate
maximum flow via residual graph sparsification. 52nd International Colloquium
on Automata, Languages, and Programming. ICALP: Automata, Languages and Programming,
LIPIcs, vol. 334, 91:1-91:20.'
mla: Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual
Graph Sparsification.” 52nd International Colloquium on Automata, Languages,
and Programming, vol. 334, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025, p. 91:1-91:20, doi:10.4230/lipics.icalp.2025.91.
short: G. Goranci, M. Henzinger, H. Räcke, A. Sricharan, in:, 52nd International
Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025, p. 91:1-91:20.
conference:
end_date: 2025-07-11
location: Aarhus, Denmark
name: 'ICALP: Automata, Languages and Programming'
start_date: 2025-07-08
corr_author: '1'
date_created: 2026-02-17T08:26:06Z
date_published: 2025-06-30T00:00:00Z
date_updated: 2026-08-20T06:28:00Z
day: '30'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/lipics.icalp.2025.91
ec_funded: 1
external_id:
arxiv:
- '2502.09105'
file:
- access_level: open_access
checksum: c178cf554e44204b9f64ebd9b54cf7ba
content_type: application/pdf
creator: dernst
date_created: 2026-02-18T09:02:33Z
date_updated: 2026-02-18T09:02:33Z
file_id: '21315'
file_name: 2025_ICALP_Goranci.pdf
file_size: 944824
relation: main_file
success: 1
file_date_updated: 2026-02-18T09:02:33Z
fulldoi: https://doi.org/10.4230/lipics.icalp.2025.91
has_accepted_license: '1'
intvolume: ' 334'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 91:1-91:20
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: 52nd International Colloquium on Automata, Languages, and Programming
publication_identifier:
isbn:
- '9783959773720'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22716'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Incremental approximate maximum flow via residual graph sparsification
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 334
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '15121'
abstract:
- lang: eng
text: We present an auction algorithm using multiplicative instead of constant weight
updates to compute a (1-E)-approximate maximum weight matching (MWM) in a bipartite
graph with n vertices and m edges in time 0(mE-1), beating the running time of
the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs
in 0(mE-1 log E-1). Our algorithm is very simple and it can be extended to give
a dynamic data structure that maintains a (1-E)-approximate maximum weight matching
under (1) one-sided vertex deletions (with incident edges) and (2) one-sided vertex
insertions (with incident edges sorted by weight) to the other side. The total
time time used is 0(mE-1), where m is the sum of the number of initially existing
and inserted edges.
acknowledgement: The first author thanks Chandra Chekuri for useful discussions about
this paper. This work was done in part at the University of Vienna. This project
has received funding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564
“The Design of Modern Fully Dynamic Data Structures (MoDynStruct)” and from the
Austrian Science Fund (FWF) project “Fast Algorithms for a Reactive Network Layer
(ReactNet)”, P 33775-N, with additional funding from the netidee SCIENCE Stiftung,
2020–2024.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Da Wei
full_name: Zheng, Da Wei
last_name: Zheng
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: Zheng DW, Henzinger M. Multiplicative auction algorithm for approximate maximum
weight bipartite matching. Mathematical Programming. 2025;210:881-894.
doi:10.1007/s10107-024-02066-3
apa: Zheng, D. W., & Henzinger, M. (2025). Multiplicative auction algorithm
for approximate maximum weight bipartite matching. Mathematical Programming.
Springer Nature. https://doi.org/10.1007/s10107-024-02066-3
chicago: Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm
for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming.
Springer Nature, 2025. https://doi.org/10.1007/s10107-024-02066-3.
ieee: D. W. Zheng and M. Henzinger, “Multiplicative auction algorithm for approximate
maximum weight bipartite matching,” Mathematical Programming, vol. 210.
Springer Nature, pp. 881–894, 2025.
ista: Zheng DW, Henzinger M. 2025. Multiplicative auction algorithm for approximate
maximum weight bipartite matching. Mathematical Programming. 210, 881–894.
mla: Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for
Approximate Maximum Weight Bipartite Matching.” Mathematical Programming,
vol. 210, Springer Nature, 2025, pp. 881–94, doi:10.1007/s10107-024-02066-3.
short: D.W. Zheng, M. Henzinger, Mathematical Programming 210 (2025) 881–894.
corr_author: '1'
das_tickbox: '0'
date_created: 2024-03-17T23:00:58Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2026-10-21T08:03:01Z
day: '01'
department:
- _id: MoHe
doi: 10.1007/s10107-024-02066-3
ec_funded: 1
external_id:
arxiv:
- '2301.09217'
isi:
- '001176048100003'
fulldoi: https://doi.org/10.1007/s10107-024-02066-3
intvolume: ' 210'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.09217
month: '03'
oa: 1
oa_version: Preprint
page: 881-894
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: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: Mathematical Programming
publication_identifier:
eissn:
- 1436-4646
issn:
- 0025-5610
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '13236'
relation: earlier_version
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Multiplicative auction algorithm for approximate maximum weight bipartite matching
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 210
year: '2025'
...
---
_id: '15093'
abstract:
- lang: eng
text: We present a dynamic data structure for maintaining the persistent homology
of a time series of real numbers. The data structure supports local operations,
including the insertion and deletion of an item and the cutting and concatenating
of lists, each in time O(log n + k), in which n counts the critical items and
k the changes in the augmented persistence diagram. To achieve this, we design
a tailor-made tree structure with an unconventional representation, referred to
as banana tree, which may be useful in its own right.
acknowledgement: The first and second authors are funded by the European Research Council under the
European Union’s Horizon 2020 research and innovation programme, ERC grant no. 788183,“Alpha
Shape Theory Extended (Alpha)”, by the Wittgenstein Prize, FWF grant no. Z 342-N31,
and by the DFG Collaborative Research Center TRR 109, FWF grant no. I 02979-N35.The
third author received funding by the European Research Council under the European
Union’s Horizon 2020research and innovation programme, ERC grant no. 101019564, “The Design of Modern Fully Dynamic DataStructures
(MoDynStruct)”, and by the Austrian Science Fund through the Wittgenstein Prize
with FWF grant no. Z 422-N, and also by FWF grant no. I 5982-N, and by FWF grant
no. P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024. The
fourth author is funded by the Vienna Graduate School on Computational Optimization,
FWF project no. W1260-N35.
article_processing_charge: No
arxiv: 1
author:
- first_name: Sebastiano
full_name: Cultrera di Montesano, Sebastiano
id: 34D2A09C-F248-11E8-B48F-1D18A9856A87
last_name: Cultrera di Montesano
orcid: 0000-0001-6249-0832
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- 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: Lara
full_name: Ost, Lara
last_name: Ost
citation:
ama: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. Dynamically maintaining
the persistent homology of time series. In: Woodruff DP, ed. Proceedings of
the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society
for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11'
apa: 'Cultrera di Montesano, S., Edelsbrunner, H., Henzinger, M., & Ost, L.
(2024). Dynamically maintaining the persistent homology of time series. In D.
P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA) (pp. 243–295). Alexandria, VA, USA: Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.11'
chicago: Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika Henzinger,
and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.”
In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied
Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
ieee: S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, and L. Ost, “Dynamically
maintaining the persistent homology of time series,” in Proceedings of the
2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria,
VA, USA, 2024, pp. 243–295.
ista: 'Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. 2024. Dynamically
maintaining the persistent homology of time series. Proceedings of the 2024 Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA: Symposium on Discrete
Algorithms, 243–295.'
mla: Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent
Homology of Time Series.” Proceedings of the 2024 Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), edited by David P. Woodruff, Society for Industrial
and Applied Mathematics, 2024, pp. 243–95, doi:10.1137/1.9781611977912.11.
short: S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P.
Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.
conference:
end_date: 2024-01-10
location: Alexandria, VA, USA
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2024-01-07
corr_author: '1'
das_tickbox: '0'
date_created: 2024-03-08T10:27:39Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2026-10-02T11:57:32Z
day: '04'
department:
- _id: HeEd
- _id: MoHe
doi: 10.1137/1.9781611977912.11
ec_funded: 1
editor:
- first_name: David P.
full_name: Woodruff, David P.
last_name: Woodruff
external_id:
arxiv:
- '2311.01115'
fulldoi: https://doi.org/10.1137/1.9781611977912.11
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2311.01115
month: '01'
oa: 1
oa_version: Preprint
page: 243 - 295
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA)
publication_identifier:
eisbn:
- '9781611977912'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '15094'
relation: dissertation_contains
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Dynamically maintaining the persistent homology of time series
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '19512'
abstract:
- lang: eng
text: "Differential privacy with gradual expiration models the setting where data
items\r\narrive in a stream and at a given time t the privacy loss guaranteed
for a data item\r\nseen at time (t − d) is εg(d), where g is a monotonically non-decreasing
function.\r\nWe study the fundamental continual (binary) counting problem where
each data\r\nitem consists of a bit, and the algorithm needs to output at each
time step the sum of\r\nall the bits streamed so far. For a stream of length T
and privacy without expiration\r\ncontinual counting is possible with maximum
(over all time steps) additive error\r\nO(log2\r\n(T)/ε) and the best known lower
bound is Ω(log(T)/ε); closing this gap\r\nis a challenging open problem.\r\nWe
show that the situation is very different for privacy with gradual expiration
by\r\ngiving upper and lower bounds for a large set of expiration functions g.
Specifically,\r\nour algorithm achieves an additive error of O(log(T)/ε) for a
large set of privacy\r\nexpiration functions. We also give a lower bound that
shows that if C is the additive\r\nerror of any ε-DP algorithm for this problem,
then the product of C and the privacy\r\nexpiration function after 2C steps must
be Ω(log(T)/ε). Our algorithm matches\r\nthis lower bound as its additive error
is O(log(T)/ε), even when g(2C) = O(1).\r\nOur empirical evaluation shows that
we achieve a slowly growing privacy loss\r\nwith significantly smaller empirical
privacy loss for large values of d than a natural\r\nbaseline algorithm."
acknowledgement: 'Monika Henzinger: This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024. Joel Daniel Andersson
and Rasmus Pagh are affiliated with Basic Algorithms Research Copenhagen (BARC),
supported by the VILLUM Foundation grant 16582, and are also supported by Providentia,
a Data Science Distinguished Investigator grant from Novo Nordisk Fonden. Teresa
Anna Steiner is supported by a research grant (VIL51463) from VILLUM FONDEN. This
work was done while Teresa Anna Steiner was a Postdoc at the Technical University
of Denmark. Jalaj Upadhyay’s research was funded by the Rutgers Decanal Grant no.
302918 and an unrestricted gift from Google.'
alternative_title:
- Advances in Neural Information Processing Systems
article_processing_charge: No
arxiv: 1
author:
- first_name: Joel Daniel
full_name: Andersson, Joel Daniel
last_name: Andersson
- 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: Rasmus
full_name: Pagh, Rasmus
last_name: Pagh
- first_name: Teresa Anna
full_name: Steiner, Teresa Anna
last_name: Steiner
- first_name: Jalaj
full_name: Upadhyay, Jalaj
last_name: Upadhyay
citation:
ama: 'Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. Continual counting
with gradual privacy expiration. In: 38th Conference on Neural Information
Processing Systems. Vol 37. Neural Information Processing Systems Foundation;
2024. doi:10.52202/079017-0299'
apa: 'Andersson, J. D., Henzinger, M., Pagh, R., Steiner, T. A., & Upadhyay,
J. (2024). Continual counting with gradual privacy expiration. In 38th Conference
on Neural Information Processing Systems (Vol. 37). Vancouver, Canada: Neural
Information Processing Systems Foundation. https://doi.org/10.52202/079017-0299'
chicago: Andersson, Joel Daniel, Monika Henzinger, Rasmus Pagh, Teresa Anna Steiner,
and Jalaj Upadhyay. “Continual Counting with Gradual Privacy Expiration.” In 38th
Conference on Neural Information Processing Systems, Vol. 37. Neural Information
Processing Systems Foundation, 2024. https://doi.org/10.52202/079017-0299.
ieee: J. D. Andersson, M. Henzinger, R. Pagh, T. A. Steiner, and J. Upadhyay, “Continual
counting with gradual privacy expiration,” in 38th Conference on Neural Information
Processing Systems, Vancouver, Canada, 2024, vol. 37.
ista: 'Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. 2024. Continual
counting with gradual privacy expiration. 38th Conference on Neural Information
Processing Systems. NeurIPS: Neural Information Processing Systems, Advances in
Neural Information Processing Systems, vol. 37.'
mla: Andersson, Joel Daniel, et al. “Continual Counting with Gradual Privacy Expiration.”
38th Conference on Neural Information Processing Systems, vol. 37, Neural
Information Processing Systems Foundation, 2024, doi:10.52202/079017-0299.
short: J.D. Andersson, M. Henzinger, R. Pagh, T.A. Steiner, J. Upadhyay, in:, 38th
Conference on Neural Information Processing Systems, Neural Information Processing
Systems Foundation, 2024.
conference:
end_date: 2024-12-15
location: Vancouver, Canada
name: 'NeurIPS: Neural Information Processing Systems'
start_date: 2024-12-09
corr_author: '1'
date_created: 2025-04-06T22:01:32Z
date_published: 2024-12-20T00:00:00Z
date_updated: 2026-10-15T09:52:07Z
day: '20'
department:
- _id: MoHe
doi: 10.52202/079017-0299
ec_funded: 1
external_id:
arxiv:
- '2406.03802'
fulldoi: https://doi.org/10.52202/079017-0299
intvolume: ' 37'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2406.03802
month: '12'
oa: 1
oa_version: Preprint
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: 38th Conference on Neural Information Processing Systems
publication_identifier:
eissn:
- 1049-5258
publication_status: published
publisher: Neural Information Processing Systems Foundation
quality_controlled: '1'
scopus_import: '1'
status: public
title: Continual counting with gradual privacy expiration
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 37
year: '2024'
...
---
_id: '15008'
abstract:
- lang: eng
text: "Oblivious routing is a well-studied paradigm that uses static precomputed
routing tables for selecting routing paths within a network. Existing oblivious
routing schemes with polylogarithmic competitive ratio for general networks are
tree-based, in the sense that routing is performed according to a convex combination
of trees. However, this restriction to trees leads to a construction that has
time quadratic in the size of the network and does not parallelize well. \r\nIn
this paper we study oblivious routing schemes based on electrical routing. In
particular, we show that general networks with n vertices and m edges admit a
routing scheme that has competitive ratio O(log² n) and consists of a convex combination
of only O(√m) electrical routings. This immediately leads to an improved construction
algorithm with time Õ(m^{3/2}) that can also be implemented in parallel with
Õ(√m) depth."
acknowledgement: "Monika Henzinger and A. R. Sricharan: This project has received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation\r\nprogramme (Grant agreement No. 101019564) and the
Austrian Science Fund (FWF) project Z\r\n422-N, project I 5982-N, and project P
33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nHarald
Räcke: Research supported by German Research Foundation (DFG), grant 470029389\r\n(FlexNets),
2021-2024.\r\nSushant Sachdeva: SS’s work is supported by an Natural Sciences and
Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2018-06398
and a Sloan Research Fellowship."
alternative_title:
- LIPIcs
article_number: '55'
article_processing_charge: No
arxiv: 1
author:
- first_name: Gramoz
full_name: Goranci, Gramoz
last_name: Goranci
- 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: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Sushant
full_name: Sachdeva, Sushant
last_name: Sachdeva
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
citation:
ama: 'Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows
for polylogarithmic competitive oblivious routing. In: 15th Innovations in
Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55'
apa: 'Goranci, G., Henzinger, M., Räcke, H., Sachdeva, S., & Sricharan, A. R.
(2024). Electrical flows for polylogarithmic competitive oblivious routing. In
15th Innovations in Theoretical Computer Science Conference (Vol. 287).
Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2024.55'
chicago: Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and
A. R. Sricharan. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.”
In 15th Innovations in Theoretical Computer Science Conference, Vol. 287.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
ieee: G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, and A. R. Sricharan, “Electrical
flows for polylogarithmic competitive oblivious routing,” in 15th Innovations
in Theoretical Computer Science Conference, Berkeley, CA, United States, 2024,
vol. 287.
ista: 'Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. 2024. Electrical
flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical
Computer Science Conference. ITCS: Innovations in Theoretical Computer Science,
LIPIcs, vol. 287, 55.'
mla: Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious
Routing.” 15th Innovations in Theoretical Computer Science Conference,
vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ITCS.2024.55.
short: G. Goranci, M. Henzinger, H. Räcke, S. Sachdeva, A.R. Sricharan, in:, 15th
Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2024.
conference:
end_date: 2024-02-02
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2024-01-30
corr_author: '1'
das_tickbox: '0'
date_created: 2024-02-18T23:01:02Z
date_published: 2024-01-24T00:00:00Z
date_updated: 2026-10-21T08:02:42Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ITCS.2024.55
ec_funded: 1
external_id:
arxiv:
- '2303.02491'
isi:
- '001300389400055'
file:
- access_level: open_access
checksum: b89716aae6a5599f187897e39de1e53a
content_type: application/pdf
creator: dernst
date_created: 2024-02-26T10:10:48Z
date_updated: 2024-02-26T10:10:48Z
file_id: '15030'
file_name: 2024_LIPICs_Goranci.pdf
file_size: 1054754
relation: main_file
success: 1
file_date_updated: 2024-02-26T10:10:48Z
fulldoi: https://doi.org/10.4230/LIPIcs.ITCS.2024.55
has_accepted_license: '1'
intvolume: ' 287'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: 15th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959773096'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Electrical flows for polylogarithmic competitive oblivious routing
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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 287
year: '2024'
...
---
_id: '14769'
abstract:
- lang: eng
text: 'For a set of points in Rd, the Euclidean k-means problems consists of finding
k centers such that the sum of distances squared from each data point to its closest
center is minimized. Coresets are one the main tools developed recently to solve
this problem in a big data context. They allow to compress the initial dataset
while preserving its structure: running any algorithm on the coreset provides
a guarantee almost equivalent to running it on the full data. In this work, we
study coresets in a fully-dynamic setting: points are added and deleted with the
goal to efficiently maintain a coreset with which a k-means solution can be computed.
Based on an algorithm from Henzinger and Kale [ESA''20], we present an efficient
and practical implementation of a fully dynamic coreset algorithm, that improves
the running time by up to a factor of 20 compared to our non-optimized implementation
of the algorithm by Henzinger and Kale, without sacrificing more than 7% on the
quality of the k-means solution.'
acknowledgement: This project has received funding from the Euro-pean Research Council (ERC) under the EuropeanUnion’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 “The De-sign of Modern Fully Dynamic Data Structures (Mo-DynStruct)” and the Austrian Science Fund (FWF)project
Z 422-N, project “Static and Dynamic Hierar-chical Graph Decompositions”, I 5982-N, and project“Fast Algorithms for a Reactive Network Layer (Re-actNet)”,
P 33775-N, with additional funding from thenetidee SCIENCE Stiftung, 2020–2024.D. Sauplic has received funding from the Euro-pean Union’s Horizon 2020 research and innovation
programme under the Marie Sklodowska-Curie grant agreementNo 101034413.
article_processing_charge: No
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: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: Leonhard
full_name: Sidl, Leonhard
id: 8b563fd0-b441-11ee-9101-a3891c61efa6
last_name: Sidl
citation:
ama: 'Henzinger M, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means
via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments. Society for Industrial and Applied Mathematics; 2024:220-233.
doi:10.1137/1.9781611977929.17'
apa: 'Henzinger, M., Saulpic, D., & Sidl, L. (2024). Experimental evaluation
of fully dynamic k-means via coresets. In 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments (pp. 220–233). Alexandria, VA, United
States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977929.17'
chicago: Henzinger, Monika, David Saulpic, and Leonhard Sidl. “Experimental Evaluation
of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments, 220–33. Society for Industrial and
Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
ieee: M. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic
k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
ista: 'Henzinger M, Saulpic D, Sidl L. 2024. Experimental evaluation of fully dynamic
k-means via coresets. 2024 Proceedings of the Symposium on Algorithm Engineering
and Experiments. ALENEX: Workshop on Algorithm Engineering and Experiments, 220–233.'
mla: Henzinger, Monika, et al. “Experimental Evaluation of Fully Dynamic K-Means
via Coresets.” 2024 Proceedings of the Symposium on Algorithm Engineering and
Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–33,
doi:10.1137/1.9781611977929.17.
short: M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium
on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics,
2024, pp. 220–233.
conference:
end_date: 2024-01-08
location: Alexandria, VA, United States
name: 'ALENEX: Workshop on Algorithm Engineering and Experiments'
start_date: 2024-01-07
corr_author: '1'
das_tickbox: '0'
date_created: 2024-01-09T16:22:47Z
date_published: 2024-01-04T00:00:00Z
date_updated: 2026-10-21T08:02:15Z
day: '04'
department:
- _id: MoHe
doi: 10.1137/1.9781611977929.17
ec_funded: 1
external_id:
arxiv:
- '2310.18034'
fulldoi: https://doi.org/10.1137/1.9781611977929.17
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2310.18034
month: '01'
oa: 1
oa_version: Preprint
page: 220-233
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments
publication_identifier:
eisbn:
- '9781611977929'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Experimental evaluation of fully dynamic k-means via coresets
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18557'
abstract:
- lang: eng
text: Broadcast and Consensus are most fundamental tasks in distributed computing.
These tasks are particularly challenging in dynamic networks where communication
across the network links may be unreliable, e.g., due to mobility or failures.
Over the last years, researchers have derived several impossibility results and
high time complexity lower bounds for these tasks. Specifically for the setting
where in each round of communication the adversary is allowed to choose one rooted
tree along which the information is disseminated, there is a lower as well as
an upper bound that is linear in the number n of nodes for Broadcast and for n
≥ 3 the adversary can guarantee that Consensus never happens. This setting is
called the oblivious message adversary for rooted trees. Also note that if the
adversary is allowed to choose a graph that does not contain a rooted tree, then
it can guarantee that Broadcast and Consensus will never happen. However, such
deterministic adversarial models may be overly pessimistic, as many processes
in real-world settings are stochastic in nature rather than worst-case. This paper
studies Broadcast on stochastic dynamic networks and shows that the situation
is very different to the deterministic case. In particular, we show that if information
dissemination occurs along random rooted trees and directed Erdős–Rényi graphs,
Broadcast completes in O(log n) rounds of communication with high probability.
The fundamental insight in our analysis is that key variables are mutually independent.
We then study two adversarial models, (a) one with Byzantine nodes and (b) one
where an adversary controls the edges. (a) Our techniques without Byzantine nodes
are general enough so that they can be extended to Byzantine nodes. (b) In the
spirit of smoothed analysis, we introduce the notion of randomized oblivious message
adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in
the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi
graph) is chosen uniformly at random among the set of all such graphs that include
these edges. We show that Broadcast completes in a finite number of rounds, which
is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All
Broadcast, and Consensus, and give lower bounds that show that most of our upper
bounds are tight.
acknowledgement: "Antoine El-Hayek: This project has received funding from the Austrian
Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the
netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received
funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon
2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian
Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant
DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung,
2020–2024.\r\nStefan Schmid: This project has received funding from the German Research
Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027."
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
- 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: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic
networks with Byzantine nodes and adversarial edges. In: 38th International
Symposium on Distributed Computing. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.DISC.2024.21'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2024). Broadcast and Consensus
in stochastic dynamic networks with Byzantine nodes and adversarial edges. In
38th International Symposium on Distributed Computing (Vol. 319). Madrid,
Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2024.21'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and
Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial
Edges.” In 38th International Symposium on Distributed Computing, Vol.
319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.DISC.2024.21.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges,” in 38th International
Symposium on Distributed Computing, Madrid, Spain, 2024, vol. 319.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges. 38th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing,
LIPIcs, vol. 319, 21.'
mla: El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks
with Byzantine Nodes and Adversarial Edges.” 38th International Symposium on
Distributed Computing, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.DISC.2024.21.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on
Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-11-01
location: Madrid, Spain
name: 'DISC: Symposium on Distributed Computing'
start_date: 2024-10-28
corr_author: '1'
das_tickbox: '0'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-24T00:00:00Z
date_updated: 2026-10-21T08:05:36Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.DISC.2024.21
ec_funded: 1
external_id:
arxiv:
- '2302.11988'
isi:
- '001542467600021'
file:
- access_level: open_access
checksum: d6c8277331cafa188c33ba1717206cf4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T08:02:45Z
date_updated: 2024-11-18T08:02:45Z
file_id: '18561'
file_name: 2024_LIPIcs_ElHayek.pdf
file_size: 809666
relation: main_file
success: 1
file_date_updated: 2024-11-18T08:02:45Z
fulldoi: https://doi.org/10.4230/LIPIcs.DISC.2024.21
has_accepted_license: '1'
intvolume: ' 319'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 38th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959773522'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes
and adversarial edges
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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 319
year: '2024'
...
---
_id: '18156'
abstract:
- lang: eng
text: Privately counting distinct elements in a stream is a fundamental data analysis
problem with many applications in machine learning. In the turnstile model, Jain
et al. [NeurIPS2023] initiated the study of this problem parameterized by the
maximum flippancy of any element, i.e., the number of times that the count of
an element changes from 0 to above 0 or vice versa. They give an item-level (ε,δ)-differentially
private algorithm whose additive error is tight with respect to that parameterization.
In this work, we show that a very simple algorithm based on the sparse vector
technique achieves a tight additive error for item-level (ε,δ)-differential privacy
and item-level ε-differential privacy with regards to a different parameterization,
namely the sum of all flippancies. Our second result is a bound which shows that
for a large class of algorithms, including all existing differentially private
algorithms for this problem, the lower bound from item-level differential privacy
extends to event-level differential privacy. This partially answers an open question
by Jain et al. [NeurIPS2023].
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (MoDynStruct,No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nTeresa Anna
Steiner: Supported by a research grant (VIL51463) from VILLUM FONDEN."
alternative_title:
- LIPIcs
article_number: '40'
article_processing_charge: No
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: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
- first_name: Teresa Anna
full_name: Steiner, Teresa Anna
last_name: Steiner
citation:
ama: 'Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements
in the turnstile model and extensions. In: International Conference on Approximation
Algorithms for Combinatorial Optimization Problems . Vol 317. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40'
apa: 'Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2024). Private counting
of distinct elements in the turnstile model and extensions. In International
Conference on Approximation Algorithms for Combinatorial Optimization Problems
(Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für
Informatik. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40'
chicago: Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “Private Counting
of Distinct Elements in the Turnstile Model and Extensions.” In International
Conference on Approximation Algorithms for Combinatorial Optimization Problems
, Vol. 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40.
ieee: M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct
elements in the turnstile model and extensions,” in International Conference
on Approximation Algorithms for Combinatorial Optimization Problems , London,
United Kingdom, 2024, vol. 317.
ista: 'Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct
elements in the turnstile model and extensions. International Conference on Approximation
Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation
Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40.'
mla: Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile
Model and Extensions.” International Conference on Approximation Algorithms
for Combinatorial Optimization Problems , vol. 317, 40, Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40.
short: M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference
on Approximation Algorithms for Combinatorial Optimization Problems , Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-08-30
location: London, United Kingdom
name: 'APPROX: Conference on Approximation Algorithms for Combinatorial Optimization
Problems'
start_date: 2024-08-27
corr_author: '1'
das_tickbox: '0'
date_created: 2024-09-29T22:01:38Z
date_published: 2024-09-16T00:00:00Z
date_updated: 2026-10-21T08:04:23Z
day: '16'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.APPROX/RANDOM.2024.40
ec_funded: 1
external_id:
arxiv:
- '2408.11637'
isi:
- '001545634500040'
file:
- access_level: open_access
checksum: c08b41c896e4d8c69570044808b40e0b
content_type: application/pdf
creator: dernst
date_created: 2024-10-01T10:07:14Z
date_updated: 2024-10-01T10:07:14Z
file_id: '18166'
file_name: 2024_LIPICs_HenzingerM.pdf
file_size: 973917
relation: main_file
success: 1
file_date_updated: 2024-10-01T10:07:14Z
fulldoi: https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40
has_accepted_license: '1'
intvolume: ' 317'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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
publication: 'International Conference on Approximation Algorithms for Combinatorial
Optimization Problems '
publication_identifier:
isbn:
- '9783959773485'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Private counting of distinct elements in the turnstile model and extensions
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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 317
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18308'
abstract:
- lang: eng
text: We study in this paper the problem of maintaining a solution to k-median and
k-means clustering in a fully dynamic setting. To do so, we present an algorithm
to efficiently maintain a coreset, a compressed version of the dataset, that allows
easy computation of a clustering solution at query time. Our coreset algorithm
has near-optimal update time of Õ(k) in general metric spaces, which reduces to
Õ(d) in the Euclidean space ℝ^d. The query time is O(k²) in general metrics, and
O(kd) in ℝ^d. To maintain a constant-factor approximation for k-median and k-means
clustering in Euclidean space, this directly leads to an algorithm with update
time Õ(d), and query time Õ(kd + k²). To maintain a O(polylog k)-approximation,
the query time is reduced to Õ(kd).
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
programme (MoDynStruct Grant agreement No. 101019564) and the Austrian Science Fund
(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
with additional funding from the netidee SCIENCE Stiftung, 2020–2024.\r\nDavid Saulpic:
Work partially done while at ISTA. Received funding from the European Union’s\r\nHorizon
2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement
No 101034413. This work was partially funded by the grant ANR-19-CE48-0016 from
the French National Research Agency (ANR)."
alternative_title:
- LIPIcs
article_number: '100'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Max Dupré
full_name: La Tour, Max Dupré
last_name: La Tour
- 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
citation:
ama: 'La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal
update time. In: 32nd Annual European Symposium on Algorithms. Vol 308.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.100'
apa: 'La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Fully dynamic k-means
coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms
(Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2024.100'
chicago: La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Fully Dynamic
K-Means Coreset in near-Optimal Update Time.” In 32nd Annual European Symposium
on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024. https://doi.org/10.4230/LIPIcs.ESA.2024.100.
ieee: M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset
in near-optimal update time,” in 32nd Annual European Symposium on Algorithms,
London, United Kingdom, 2024, vol. 308.
ista: 'La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in
near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European
Symposium on Algorithms, LIPIcs, vol. 308, 100.'
mla: La Tour, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update
Time.” 32nd Annual European Symposium on Algorithms, vol. 308, 100, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.100.
short: M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium
on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-04
location: London, United Kingdom
name: 'ESA: European Symposium on Algorithms'
start_date: 2024-09-02
corr_author: '1'
das_tickbox: '0'
date_created: 2024-10-13T22:01:50Z
date_published: 2024-09-23T00:00:00Z
date_updated: 2026-10-21T08:04:40Z
day: '23'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2024.100
ec_funded: 1
external_id:
arxiv:
- '2406.19926'
isi:
- '001545622400100'
file:
- access_level: open_access
checksum: 8e8c0b13049f11bb0133dfac22e32718
content_type: application/pdf
creator: dernst
date_created: 2024-10-21T09:41:48Z
date_updated: 2024-10-21T09:41:48Z
file_id: '18454'
file_name: 2024_LIPICs_DuprelaTour.pdf
file_size: 873561
relation: main_file
success: 1
file_date_updated: 2024-10-21T09:41:48Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2024.100
has_accepted_license: '1'
intvolume: ' 308'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 32nd Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959773386'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Fully dynamic k-means coreset in near-optimal update time
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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 308
year: '2024'
...
---
_id: '18115'
abstract:
- lang: eng
text: "We study the data selection problem, whose aim is to select a small representative
subset of data that can be used to efficiently train a machine learning model.
We present a new data selection approach based on k-means clustering and sensitivity
sampling. Assuming access to an embedding representation of the data with respect
to which the model loss is Holder continuous, our approach provably allows selecting
a set of “typical” k+1/ε2 elements whose average loss corresponds to the average
loss of the whole dataset, up to a multiplicative (1±ε)\r\n factor and an additive
ελΦk, where Φk represents the k-means cost for the input embeddings and λ is the
Holder constant. We furthermore demonstrate the performance and scalability of
our approach on fine-tuning foundation models and show that it outperforms state-of-the-art
methods. We also show how it can be applied on linear regression, leading to a
new sampling strategy that surprisingly matches the performance of leverage score
sampling, while being conceptually simpler and more scalable."
acknowledgement: "Monika Henzinger: This project has received funding from the European
Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant agreement No. 101019564) and the Austrian Science Fund (FWF) grant
DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with
additional funding from the netidee SCIENCE Stiftung, 2020–2024. This work was partially
done while David Saulpic was at the Institute for Science and Technology, Austria
(ISTA). David Sauplic has received funding from the European Union’s Horizon 2020
research and innovation programme under the\r\nMarie Sklodowska-Curie grant agreement
No 101034413. Work was done while David Woodruff was visiting Google Research."
alternative_title:
- PMLR
article_processing_charge: No
arxiv: 1
author:
- first_name: Kyriakos
full_name: Axiotis, Kyriakos
last_name: Axiotis
- first_name: Vincent
full_name: Cohen-Addad, Vincent
last_name: Cohen-Addad
- 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: Sammy
full_name: Jerome, Sammy
last_name: Jerome
- first_name: Vahab
full_name: Mirrokni, Vahab
last_name: Mirrokni
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: David P.
full_name: Woodruff, David P.
last_name: Woodruff
- first_name: Michael
full_name: Wunder, Michael
last_name: Wunder
citation:
ama: 'Axiotis K, Cohen-Addad V, Henzinger M, et al. Data-efficient learning via
clustering-based sensitivity sampling: Foundation models and beyond. In: Proceedings
of the 41st International Conference on Machine Learning. Vol 235. ML Research
Press; 2024:2086-2107.'
apa: 'Axiotis, K., Cohen-Addad, V., Henzinger, M., Jerome, S., Mirrokni, V., Saulpic,
D., … Wunder, M. (2024). Data-efficient learning via clustering-based sensitivity
sampling: Foundation models and beyond. In Proceedings of the 41st International
Conference on Machine Learning (Vol. 235, pp. 2086–2107). Vienna, Austria:
ML Research Press.'
chicago: 'Axiotis, Kyriakos, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome,
Vahab Mirrokni, David Saulpic, David P. Woodruff, and Michael Wunder. “Data-Efficient
Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.”
In Proceedings of the 41st International Conference on Machine Learning,
235:2086–2107. ML Research Press, 2024.'
ieee: 'K. Axiotis et al., “Data-efficient learning via clustering-based sensitivity
sampling: Foundation models and beyond,” in Proceedings of the 41st International
Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 2086–2107.'
ista: 'Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff
DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling:
Foundation models and beyond. Proceedings of the 41st International Conference
on Machine Learning. ICML: International Conference on Machine Learning, PMLR,
vol. 235, 2086–2107.'
mla: 'Axiotis, Kyriakos, et al. “Data-Efficient Learning via Clustering-Based Sensitivity
Sampling: Foundation Models and Beyond.” Proceedings of the 41st International
Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 2086–107.'
short: K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic,
D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference
on Machine Learning, ML Research Press, 2024, pp. 2086–2107.
conference:
end_date: 2024-07-27
location: Vienna, Austria
name: 'ICML: International Conference on Machine Learning'
start_date: 2024-07-21
das_tickbox: '0'
date_created: 2024-09-22T22:01:44Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2026-10-21T08:03:43Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
ec_funded: 1
external_id:
arxiv:
- '2402.17327'
intvolume: ' 235'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2402.17327
month: '09'
oa: 1
oa_version: Published Version
page: 2086-2107
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 41st International Conference on Machine Learning
publication_identifier:
eissn:
- 2640-3498
publication_status: published
publisher: ML Research Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Data-efficient learning via clustering-based sensitivity sampling: Foundation
models and beyond'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 235
year: '2024'
...