---
OA_place: publisher
OA_type: gold
_id: '22004'
abstract:
- lang: eng
text: "Recent research on computing the diameter of geometric intersection graphs
has made significant strides, primarily focusing on the 2D case [Duraj et al.,
2024; Hsien-Chih Chang et al., 2024; Chan et al., 2025] where truly subquadratic-time
algorithms were given for simple objects such as unit-disks and (axis-aligned)
squares. However, in three or higher dimensions, there is no known truly subquadratic-time
algorithm for any intersection graph of non-trivial objects, even basic ones such
as unit balls or (axis-aligned) unit cubes. This was partially explained by the
pioneering work of Bringmann et al. [Karl Bringmann et al., 2022] which gave several
truly subquadratic lower bounds, notably for unit balls or unit cubes in 3D when
the graph diameter Δ is at least Ω(log n), hinting at a pessimistic outlook for
the complexity of the diameter problem in higher dimensions. In this paper, we
substantially extend the landscape of diameter computation for objects in three
and higher dimensions, giving a few positive results. Our highlighted findings
include: \r\n1) A truly subquadratic-time algorithm for deciding if the diameter
of unit cubes in 3D is at most 3 (Diameter-3 hereafter), the first algorithm of
its kind for objects in 3D or higher dimensions. Our algorithm is based on a novel
connection to pseudolines, which is of independent interest. \r\n2) A truly subquadratic
time lower bound for Diameter-3 of unit balls in 3D under the Orthogonal Vector
(OV) hypothesis, giving the first separation between unit balls and unit cubes
in the small diameter regime. Previously, computing the diameter for both objects
was known to be quadratic hard when the diameter is Ω(log n) [Karl Bringmann et
al., 2022]. \r\n3) A near-linear-time algorithm for Diameter-2 of unit cubes in
3D, generalizing the previous result for unit squares in 2D [Karl Bringmann et
al., 2022]. \r\n4) A truly subquadratic-time algorithm and lower bound for Diameter-2
and Diameter-3 of rectangular boxes (of arbitrary dimension and sizes), respectively."
acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih
Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271,
DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported
by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF
grant CCF-2517033 and an NSF CAREER Award CCF-2237288. Da Wei Zheng: This project
has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982.
For open access purposes, the author has applied a CC BY public copyright license
to any author-accepted manuscript version arising from this submission."
alternative_title:
- LIPIcs
article_number: 29:1-29:15
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Timothy M.
full_name: Chan, Timothy M.
last_name: Chan
- first_name: Hsien Chih
full_name: Chang, Hsien Chih
last_name: Chang
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
- first_name: Sándor
full_name: Kisfaludi-Bak, Sándor
last_name: Kisfaludi-Bak
- first_name: Hung
full_name: Le, Hung
last_name: Le
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the diameter
computation landscape of intersection graphs in 3D and above. In: 42nd International
Symposium on Computational Geometry. Vol 367. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2026. doi:10.4230/LIPIcs.SoCG.2026.29'
apa: 'Chan, T. M., Chang, H. C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng,
D. W. (2026). Charting the diameter computation landscape of intersection graphs
in 3D and above. In 42nd International Symposium on Computational Geometry
(Vol. 367). New Brunswick, NJ, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2026.29'
chicago: Chan, Timothy M., Hsien Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung
Le, and Da Wei Zheng. “Charting the Diameter Computation Landscape of Intersection
Graphs in 3D and Above.” In 42nd International Symposium on Computational Geometry,
Vol. 367. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.SoCG.2026.29.
ieee: T. M. Chan, H. C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng,
“Charting the diameter computation landscape of intersection graphs in 3D and
above,” in 42nd International Symposium on Computational Geometry, New
Brunswick, NJ, United States, 2026, vol. 367.
ista: 'Chan TM, Chang HC, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting
the diameter computation landscape of intersection graphs in 3D and above. 42nd
International Symposium on Computational Geometry. SoCG: Symposium on Computational
Geometry, LIPIcs, vol. 367, 29:1-29:15.'
mla: Chan, Timothy M., et al. “Charting the Diameter Computation Landscape of Intersection
Graphs in 3D and Above.” 42nd International Symposium on Computational Geometry,
vol. 367, 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026,
doi:10.4230/LIPIcs.SoCG.2026.29.
short: T.M. Chan, H.C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:,
42nd International Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026.
conference:
end_date: 2026-06-05
location: New Brunswick, NJ, United States
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2026-06-02
corr_author: '1'
das_tickbox: '0'
date_created: 2026-06-14T22:01:44Z
date_published: 2026-05-27T00:00:00Z
date_updated: 2026-06-22T08:37:44Z
day: '27'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.SoCG.2026.29
external_id:
arxiv:
- '2603.21790'
file:
- access_level: open_access
checksum: ffff03934cc182757d6db82d88f896e6
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T08:34:11Z
date_updated: 2026-06-22T08:34:11Z
file_id: '22114'
file_name: 2026_LIPIcSSoCG_Chan.pdf
file_size: 918197
relation: main_file
success: 1
file_date_updated: 2026-06-22T08:34:11Z
fulldoi: https://doi.org/10.4230/LIPIcs.SoCG.2026.29
has_accepted_license: '1'
intvolume: ' 367'
keyword:
- Graph Diameter
- Geometric Intersection Graphs
- Unit Ball Graphs
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 42nd International Symposium on Computational Geometry
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774185'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Charting the diameter computation landscape of intersection graphs in 3D and
above
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: 367
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21159'
abstract:
- lang: eng
text: "One of the foundational theorems of extremal graph theory is Dirac’s theorem,
which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then
G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later
work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have
many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler
and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles
and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter
of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings
in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let
md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching
in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to
determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless
able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex
k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any
constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan
entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof
Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin."
acknowledgement: We would like to thank the referees for a number of helpful comments
and suggestions, which have substantially improved the paper. Open access funding
provided by Institute of Science and Technology (IST Austria).
article_number: '5'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Yiting
full_name: Wang, Yiting
id: 1917d194-076e-11ed-97cd-837255f88785
last_name: Wang
orcid: 0000-0002-2856-767X
citation:
ama: Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs.
Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8
apa: Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings
in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8
chicago: Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting
Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature,
2026. https://doi.org/10.1007/s00493-025-00194-8.
ieee: M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in
Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.
ista: Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac
hypergraphs. Combinatorica. 46, 5.
mla: Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.”
Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.
short: M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).
corr_author: '1'
date_created: 2026-02-08T23:02:49Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-02-16T09:55:17Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
- _id: MoHe
doi: 10.1007/s00493-025-00194-8
external_id:
arxiv:
- '2408.09589'
file:
- access_level: open_access
checksum: 47b0031d90b0e6b9a843f422a1486089
content_type: application/pdf
creator: dernst
date_created: 2026-02-16T09:52:38Z
date_updated: 2026-02-16T09:52:38Z
file_id: '21228'
file_name: 2026_Combinatorica_Kwan.pdf
file_size: 539646
relation: main_file
success: 1
file_date_updated: 2026-02-16T09:52:38Z
fulldoi: https://doi.org/10.1007/s00493-025-00194-8
has_accepted_license: '1'
intvolume: ' 46'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting perfect matchings in Dirac hypergraphs
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: 46
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21719'
abstract:
- lang: eng
text: "We develop a new algorithmic framework for designing approximation algorithms
for cut-based optimization problems on capacitated undirected graphs that undergo
edge insertions and deletions. Specifically, our framework dynamically maintains
a variant of the hierarchical \U0001D457-tree decomposition of [Madry FOCS’10],
achieving a poly-logarithmic approximation factor to the graph’s cut structure
and supporting edge updates in \U0001D442(\U0001D45B\U0001D700) amortized update
time, for any arbitrarily small constant \U0001D700 ∈(0,1).\r\nConsequently, we
obtain new trade-offs between approximation and update/query time for fundamental
cut-based optimization problems in the fully dynamic setting, including all-pairs
minimum cuts, sparsest cut, multi-way cut, and multi-cut. For the last three problems,
these trade-offs give the first fully-dynamic algorithms achieving poly-logarithmic
approximation in sub-linear time per operation.\r\nThe main technical ingredient
behind our dynamic hierarchy is a dynamic cut-sparsifier algorithm that can handle
vertex splits with low recourse. This is achieved by white-boxing the dynamic
cut sparsifier construction of [Abraham et al. FOCS’16], based on forest packing,
together with new structural insights about the maintenance of these forests under
vertex splits. Given the versatility of cut sparsification in both the static
and dynamic graph algorithms literature, we believe this construction may be of
independent interest."
acknowledgement: "Monika Henzinger: Funded by the European union. Views and opinions
expressed\r\nare however those of the author(s) only and do not necessarily reflect
those of the European Union or the European Research Council Executive Agency. Neither
the European Union nor the granting authority can be held responsible for them.
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. For
open access purposes, the author has applied a CC BY public copyright license to
any author accepted manuscript version arising from this submission.\r\nPeter Kiss:
This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/ESP6088024."
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: Peter
full_name: Kiss, Peter
last_name: Kiss
- first_name: Ali
full_name: Momeni, Ali
last_name: Momeni
- first_name: Gernot
full_name: Zöcklein, Gernot
id: 45d5e826-47af-11f1-84e5-ba87c23fe681
last_name: Zöcklein
citation:
ama: 'Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. Dynamic hierarchical
j-tree decomposition and its applications. In: Proceedings of the 2026 Annual
ACM SIAM Symposium on Discrete Algorithms. Vol 2026-January. Society for Industrial
and Applied Mathematics; 2026:1128-1180. doi:10.1137/1.9781611978971.45'
apa: Goranci, G., Henzinger, M., Kiss, P., Momeni, A., & Zöcklein, G. (2026).
Dynamic hierarchical j-tree decomposition and its applications. In Proceedings
of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms (Vol. 2026–January,
pp. 1128–1180). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978971.45
chicago: Goranci, Gramoz, Monika Henzinger, Peter Kiss, Ali Momeni, and Gernot Zöcklein.
“Dynamic Hierarchical J-Tree Decomposition and Its Applications.” In Proceedings
of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, 2026–January:1128–80.
Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.45.
ieee: G. Goranci, M. Henzinger, P. Kiss, A. Momeni, and G. Zöcklein, “Dynamic hierarchical
j-tree decomposition and its applications,” in Proceedings of the 2026 Annual
ACM SIAM Symposium on Discrete Algorithms, 2026, vol. 2026–January, pp. 1128–1180.
ista: 'Goranci G, Henzinger M, Kiss P, Momeni A, Zöcklein G. 2026. Dynamic hierarchical
j-tree decomposition and its applications. Proceedings of the 2026 Annual ACM
SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms
vol. 2026–January, 1128–1180.'
mla: Goranci, Gramoz, et al. “Dynamic Hierarchical J-Tree Decomposition and Its
Applications.” Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete
Algorithms, vol. 2026–January, Society for Industrial and Applied Mathematics,
2026, pp. 1128–80, doi:10.1137/1.9781611978971.45.
short: G. Goranci, M. Henzinger, P. Kiss, A. Momeni, G. Zöcklein, in:, Proceedings
of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial
and Applied Mathematics, 2026, pp. 1128–1180.
conference:
name: 'SODA: Symposium on Discrete Algorithms'
date_created: 2026-04-12T22:01:51Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-05-04T11:54:09Z
day: '07'
department:
- _id: MoHe
doi: 10.1137/1.9781611978971.45
ec_funded: 1
external_id:
arxiv:
- '2601.09139'
fulldoi: https://doi.org/10.1137/1.9781611978971.45
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2601.09139
month: '01'
oa: 1
oa_version: Preprint
page: 1128-1180
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
publication: Proceedings of the 2026 Annual ACM SIAM Symposium on Discrete Algorithms
publication_identifier:
eissn:
- '15579468'
isbn:
- '9781611978971'
issn:
- '10719040'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dynamic hierarchical j-tree decomposition and its applications
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2026-January
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22246'
abstract:
- lang: eng
text: "In this paper we construct distance sketches for intersection graphs of arbitrary
path-connected regions in the plane (known as the string graphs) in the constant
and 1+ε distortion regimes. Furthermore, the distance sketches themselves are
planar graphs. First, we show that every unweighted string graph G has an O(1)-distortion
planar emulator: that is, there exists an edge-weighted planar graph H containing
every vertex in G, such that every pair of vertices (u,v) satisfies δG(u,v) ≤
δH(u,v) ≤ O(1) · δG(u,v). Furthermore, we show that for any constant ε > 0, there
is an edge-weighted planar graph H′ such that every pair of vertices (u,v) satisfies
δG(u,v) ≤ δH′(u,v) ≤ (1+ε) · δG(u,v) + O(ε−4polylogn). No previous constructions
of sparse distance sketches were known even for intersection graphs of simple
shapes like axis-parallel rectangles or fat convex polygons.\r\nAs applications,
we construct the first (1+ε, +O(1)) mixed-distortion tree cover and distance oracle
for arbitrary string graphs, as well as the first additive +(εΔ+O(1))-distortion
embedding of string graphs G with diameter Δ into graphs of constant treewidth
O(ε−4)."
acknowledgement: "Hsien-Chih Chang and Jonathan Conroy are supported by the U.S.\r\nNational
Science Foundation CAREER Award under the Grant No.\r\nCCF-2443017."
article_processing_charge: No
arxiv: 1
author:
- first_name: Hsien Chih
full_name: Chang, Hsien Chih
last_name: Chang
- first_name: Jonathan
full_name: Conroy, Jonathan
last_name: Conroy
- first_name: Zihan
full_name: Tan, Zihan
last_name: Tan
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Chang HC, Conroy J, Tan Z, Zheng DW. Cutting planarians: Planar emulators
for string graphs. In: 58th Annual ACM Symposium on Theory of Computing.
Association for Computing Machinery; 2026:2140-2151. doi:10.1145/3798129.3800917'
apa: 'Chang, H. C., Conroy, J., Tan, Z., & Zheng, D. W. (2026). Cutting planarians:
Planar emulators for string graphs. In 58th Annual ACM Symposium on Theory
of Computing (pp. 2140–2151). Salt Lake City, UT, United States: Association
for Computing Machinery. https://doi.org/10.1145/3798129.3800917'
chicago: 'Chang, Hsien Chih, Jonathan Conroy, Zihan Tan, and Da Wei Zheng. “Cutting
Planarians: Planar Emulators for String Graphs.” In 58th Annual ACM Symposium
on Theory of Computing, 2140–51. Association for Computing Machinery, 2026.
https://doi.org/10.1145/3798129.3800917.'
ieee: 'H. C. Chang, J. Conroy, Z. Tan, and D. W. Zheng, “Cutting planarians: Planar
emulators for string graphs,” in 58th Annual ACM Symposium on Theory of Computing,
Salt Lake City, UT, United States, 2026, pp. 2140–2151.'
ista: 'Chang HC, Conroy J, Tan Z, Zheng DW. 2026. Cutting planarians: Planar emulators
for string graphs. 58th Annual ACM Symposium on Theory of Computing. STOC: Symposium
on the Theory of Computing, 2140–2151.'
mla: 'Chang, Hsien Chih, et al. “Cutting Planarians: Planar Emulators for String
Graphs.” 58th Annual ACM Symposium on Theory of Computing, Association
for Computing Machinery, 2026, pp. 2140–51, doi:10.1145/3798129.3800917.'
short: H.C. Chang, J. Conroy, Z. Tan, D.W. Zheng, in:, 58th Annual ACM Symposium
on Theory of Computing, Association for Computing Machinery, 2026, pp. 2140–2151.
conference:
end_date: 2026-06-26
location: Salt Lake City, UT, United States
name: 'STOC: Symposium on the Theory of Computing'
start_date: 2026-06-22
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-05T22:01:37Z
date_published: 2026-06-09T00:00:00Z
date_updated: 2026-07-06T10:25:23Z
day: '09'
ddc:
- '500'
- '000'
department:
- _id: MoHe
doi: 10.1145/3798129.3800917
external_id:
arxiv:
- '2510.21700'
file:
- access_level: open_access
checksum: c184596a3e18fee912caef4c7751a96d
content_type: application/pdf
creator: dernst
date_created: 2026-07-06T10:23:09Z
date_updated: 2026-07-06T10:23:09Z
file_id: '22253'
file_name: 2026_STOC_Chang.pdf
file_size: 2015699
relation: main_file
success: 1
file_date_updated: 2026-07-06T10:23:09Z
fulldoi: https://doi.org/10.1145/3798129.3800917
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2140-2151
publication: 58th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400725364'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: 'Cutting planarians: Planar emulators for string graphs'
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: '2026'
...
---
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: '22322'
abstract:
- lang: eng
text: "We study the problem of continually releasing statistics of an evolving dataset
under differential privacy. In the event-level setting, we show the first polynomial
lower bounds on the additive error for insertions-only graph problems such as
maximum matching, degree histogram and k-core number computation. These results
represent an exponential improvement on the polylogarithmic lower bounds of Fichtenberger,
Henzinger and Ost [ESA 2021] for the former two problems, and are the first lower
bounds in the continual release setting for the latter problem. Our results run
counter to the intuition that the difference between insertions-only vs fully
dynamic updates causes the gap between polylogarithmic and polynomial additive
error. Indeed, we show that for estimating the size of the maximum matching or
k-core number of a vertex, allowing small multiplicative approximations is what
brings the additive error down to polylogarithmic. We complement these results
with improved upper bounds on the additive error when no multiplicative approximation
is allowed.\r\nBeyond graphs, our techniques also show that polynomial additive
error is unavoidable for the Simultaneous Norm Estimation problem in the insertions-only
setting. When multiplicative approximations are allowed, we circumvent this lower
bound by giving the first continual mechanism with polylogarithmic additive error
under (1 + ζ) multiplicative approximations, for any ζ > 0, for estimating all
monotone symmetric norms simultaneously.\r\nIn the item-level setting, we show
polynomial lower bounds on the product of the multiplicative and the additive
error of continual mechanisms for a large range of graph problems. To the best
of our knowledge, these are the first lower bounds shown for any differentially
private mechanism under continual release with multiplicative error. To obtain
these results, we prove a new lower bound on the product of multiplicative and
additive error for the 1-Way-Marginals problem, and give reductions from 1-Way-Marginals
to our desired graph problems. This generalizes the prior results of Hardt and
Talwar [STOC 2010] and Bun, Ullman and Vadhan [STOC 2014, SIAM J. Comput. 2018],
who gave lower bounds on the additive error for the special case of mechanisms
with no multiplicative error."
acknowledgement: "Bardiya Aryanfard and Monika Henzinger were supported by the European
Research Council (ERC)\r\nunder the European Union’s Horizon 2020 research and innovation
programme (Grant agreement\r\nNo. 101019564). For open access purposes, the author
has applied a CC BY public copyright\r\nlicense to any author-accepted manuscript
version arising from this submission. Funded by the\r\nEuropean union. Views and
opinions expressed are however those of the author(s) only and do\r\nnot necessarily
reflect those of the European Union or the European Research Council Executive\r\nAgency.
Neither the European Union nor the granting authority can be held responsible for
them"
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Bardiya
full_name: Aryanfard, Bardiya
id: 1e8f4084-31df-11ee-b195-f706b4b77091
last_name: Aryanfard
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: David
full_name: Saulpic, David
id: f8e48cf0-b0ff-11ed-b0e9-b4c35598f964
last_name: Saulpic
- first_name: A. R.
full_name: Sricharan, A. R.
last_name: Sricharan
citation:
ama: Aryanfard B, Henzinger M, Saulpic D, Sricharan AR. Improved lower bounds for
privacy under continual release. Proceedings of the ACM on Management of Data.
2026;4(2):1-27. doi:10.1145/3801903
apa: Aryanfard, B., Henzinger, M., Saulpic, D., & Sricharan, A. R. (2026). Improved
lower bounds for privacy under continual release. Proceedings of the ACM on
Management of Data. Association for Computing Machinery. https://doi.org/10.1145/3801903
chicago: Aryanfard, Bardiya, Monika Henzinger, David Saulpic, and A. R. Sricharan.
“Improved Lower Bounds for Privacy under Continual Release.” Proceedings of
the ACM on Management of Data. Association for Computing Machinery, 2026.
https://doi.org/10.1145/3801903.
ieee: B. Aryanfard, M. Henzinger, D. Saulpic, and A. R. Sricharan, “Improved lower
bounds for privacy under continual release,” Proceedings of the ACM on Management
of Data, vol. 4, no. 2. Association for Computing Machinery, pp. 1–27, 2026.
ista: Aryanfard B, Henzinger M, Saulpic D, Sricharan AR. 2026. Improved lower bounds
for privacy under continual release. Proceedings of the ACM on Management of Data.
4(2), 1–27.
mla: Aryanfard, Bardiya, et al. “Improved Lower Bounds for Privacy under Continual
Release.” Proceedings of the ACM on Management of Data, vol. 4, no. 2,
Association for Computing Machinery, 2026, pp. 1–27, doi:10.1145/3801903.
short: B. Aryanfard, M. Henzinger, D. Saulpic, A.R. Sricharan, Proceedings of the
ACM on Management of Data 4 (2026) 1–27.
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-14T05:33:58Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-07-16T09:30:31Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1145/3801903
ec_funded: 1
external_id:
arxiv:
- '2512.15981'
file:
- access_level: open_access
checksum: 21a48a620e415a31a3874077c55bc6c3
content_type: application/pdf
creator: dernst
date_created: 2026-07-16T09:29:08Z
date_updated: 2026-07-16T09:29:08Z
file_id: '22349'
file_name: 2026_ACMMgmtData_Aryanfard.pdf
file_size: 934963
relation: main_file
success: 1
file_date_updated: 2026-07-16T09:29:08Z
fulldoi: https://doi.org/10.1145/3801903
has_accepted_license: '1'
intvolume: ' 4'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 1-27
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
publication: Proceedings of the ACM on Management of Data
publication_identifier:
issn:
- 2836-6573
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Improved lower bounds for privacy under continual release
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 4
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22368'
abstract:
- lang: eng
text: "We study simple dynamics in the population protocol model, in\r\nwhich \U0001D45B
agents start with totally ordered initial opinions \U0001D4651, \U0001D4652, .
. . ,\r\n\U0001D465\U0001D45B and, in each round, a randomly chosen agent changes
its opinion\r\nas a function of the opinion of other randomly chosen agents. Such\r\ndynamics
often converge to consensus on a single fixation value \U0001D44Bˆ.\r\nThis paper
asks how to control the distribution of \U0001D44Bˆ as a randomised\r\nchoice
among the initial opinions by designing suitable simple\r\ndynamics. Writing the
sorted initial values as \U0001D465(1) ≤ · · · ≤ \U0001D465(\U0001D45B)\r\n,\r\nwe
design two protocols that realise natural target laws over order\r\nstatistics.\r\nFirst,
for a parameter \U0001D45D ∈ (0, 1), our geometric protocol biases\r\ntoward larger
opinions and satisfies P\r\n\r\n\U0001D44Bˆ = \U0001D465(\U0001D458)\r\n\r\n∝
\U0001D45D\r\n\U0001D45B−\U0001D458\r\n, for\r\n\U0001D458 = 1, . . . , \U0001D45B.
Equivalently, P\r\n\r\n\U0001D44Bˆ = \U0001D465(\U0001D458)\r\n\r\n= (1 − \U0001D45D)\U0001D45D\r\n\U0001D45B−\U0001D458\r\n/(1
− \U0001D45D\r\n\U0001D45B\r\n).\r\nSecond, our binomial protocol assigns a shifted
binomial law to the\r\nranks in ascending order: if \U0001D43E −1 ∼ Bin(\U0001D45B−1,
1−\U0001D45D), then \U0001D44Bˆ = \U0001D465(\U0001D43E)\r\n,\r\ni.e., P\r\n\r\n\U0001D44Bˆ
= \U0001D465(\U0001D458)\r\n\r\n=\r\n\U0001D45B−1\r\n\U0001D458−1\r\n\x01\r\n\U0001D45D\r\n\U0001D45B−\U0001D458\r\n(1
− \U0001D45D)\r\n\U0001D458−1\r\n, for \U0001D458 = 1, . . . , \U0001D45B.\r\nApplications
of this include computing the Top-\U0001D458 values for\r\nsmall \U0001D458 on
general interaction graphs. A central contribution of\r\nthis work is that, in
contrast to most population protocols, we can\r\ncharacterise the fixation distribution
in closed form. This is enabled\r\nby a novel analysis technique, which also yields
applications: we\r\nderive new results for the Median protocol that extend the
state of\r\nthe art."
acknowledgement: "This work has been supported by the AID INRIA-DGA project\r\nn°2023000872
“BioSwarm”, the French government National Research Agency (ANR) through the UCA
JEDI (ANR-15-IDEX-01),\r\nthe EUR DS4H (ANR-17-EURE-004) and the 3IA Cote d’Azur
Investments ANR-23-IACL-0001, and EPSRC grant EP/W005573/1"
article_processing_charge: No
author:
- first_name: Niccolò
full_name: D'Archivio, Niccolò
last_name: D'Archivio
- first_name: Hind
full_name: Almahmoud, Hind
last_name: Almahmoud
- first_name: Emanuele
full_name: Natale, Emanuele
last_name: Natale
- first_name: Frederik
full_name: Mallmann-Trenn, Frederik
id: 68748c44-84d5-11f1-b4f6-ca083374e553
last_name: Mallmann-Trenn
citation:
ama: 'D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. Order statistics in
population protocols via simple dynamics. In: Proceedings of the Annual ACM
Symposium on Principles of Distributed Computing. Association for Computing
Machinery; 2026:425-436. doi:10.1145/3796701.3815922'
apa: 'D’Archivio, N., Almahmoud, H., Natale, E., & Mallmann-Trenn, F. (2026).
Order statistics in population protocols via simple dynamics. In Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing (pp. 425–436).
Egham, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815922'
chicago: D’Archivio, Niccolò, Hind Almahmoud, Emanuele Natale, and Frederik Mallmann-Trenn.
“Order Statistics in Population Protocols via Simple Dynamics.” In Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, 425–36.
Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815922.
ieee: N. D’Archivio, H. Almahmoud, E. Natale, and F. Mallmann-Trenn, “Order statistics
in population protocols via simple dynamics,” in Proceedings of the Annual
ACM Symposium on Principles of Distributed Computing, Egham, United Kingdom,
2026, pp. 425–436.
ista: 'D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. 2026. Order statistics
in population protocols via simple dynamics. Proceedings of the Annual ACM Symposium
on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 425–436.'
mla: D’Archivio, Niccolò, et al. “Order Statistics in Population Protocols via Simple
Dynamics.” Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2026, pp. 425–36, doi:10.1145/3796701.3815922.
short: N. D’Archivio, H. Almahmoud, E. Natale, F. Mallmann-Trenn, in:, Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, Association
for Computing Machinery, 2026, pp. 425–436.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2026-07-06
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-19T22:01:47Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-21T07:34:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3796701.3815922
file:
- access_level: open_access
checksum: e8208393a016d8e71d7b26c402045488
content_type: application/pdf
creator: dernst
date_created: 2026-07-21T07:31:29Z
date_updated: 2026-07-21T07:31:29Z
file_id: '22379'
file_name: 2026_ACMPODC_dArchivio.pdf
file_size: 824239
relation: main_file
success: 1
file_date_updated: 2026-07-21T07:31:29Z
fulldoi: https://doi.org/10.1145/3796701.3815922
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 425-436
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9798400725128'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Order statistics in population protocols via simple dynamics
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: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22367'
abstract:
- lang: eng
text: "We study the Undecided-State Dynamics (USD), a fundamental consensus process
in which each vertex holds one of k decided opinions or the undecided state. We
consider both the gossip model and the population protocol model. Prior work established
tight bounds on the consensus time of this process only for the regime \r\nk\r\n=\r\nO\r\n(\r\nn\r\n/\r\n(\r\nlog\r\n\r\nn\r\n)\r\n2\r\n)\r\n
(for the population protocol model) and k = O((n/log n)1/3) (for the gossip model),
often under restrictive assumptions on the initial configuration.\r\nIn this paper,
we obtain the first consensus-time guarantees for USD that hold for arbitrary
2 ≤ k ≤ n and for arbitrary initial configurations in both the gossip model and
the population protocol model. In the gossip model, USD reaches consensus within
\r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\n,\r\nn\r\n}\r\n)\r\n synchronous rounds with
probability 1 - p⊥ - n-c, where p⊥ is the gossip-specific probability of collapsing
to the all-undecided state in the first round. In the population protocol model,
USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\nn\r\n,\r\nn\r\n3\r\n/\r\n2\r\n}\r\n)\r\n
asynchronous interactions with high probability. We also present lower bounds
that match the upper bounds up to polylogarithmic factors for a specific initial
configuration and show that our upper bounds are essentially optimal."
acknowledgement: "Nobutaka Shimizu is supported by JSPS KAKENHI Grant Number\r\n23K16837.
Takeharu Shiraga is supported by JSPS KAKENHI Grant\r\nNumber 23K16840, and JST
CRONOS Grant Number JPMJCS24K2.\r\nColin Cooper is supported by a Mercator Fellowship
from DFG\r\nProject 491453517 at the University of Hamburg. We thank the\r\nanonymous
reviewers for their helpful comments and suggestions."
article_processing_charge: No
arxiv: 1
author:
- first_name: Colin
full_name: Cooper, Colin
last_name: Cooper
- first_name: Frederik
full_name: Mallmann-Trenn, Frederik
id: 68748c44-84d5-11f1-b4f6-ca083374e553
last_name: Mallmann-Trenn
- first_name: Tomasz
full_name: Radzik, Tomasz
last_name: Radzik
- first_name: Nobutaka
full_name: Shimizu, Nobutaka
last_name: Shimizu
- first_name: Takeharu
full_name: Shiraga, Takeharu
last_name: Shiraga
citation:
ama: 'Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. Undecided state
dynamics with many opinions. In: Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing. Association for Computing Machinery;
2026:77-87. doi:10.1145/3796701.3815920'
apa: 'Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., & Shiraga, T.
(2026). Undecided state dynamics with many opinions. In Proceedings of the
Annual ACM Symposium on Principles of Distributed Computing (pp. 77–87). Egham,
United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815920'
chicago: Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu,
and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, 77–87.
Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815920.
ieee: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided
state dynamics with many opinions,” in Proceedings of the Annual ACM Symposium
on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 77–87.
ista: 'Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. 2026. Undecided
state dynamics with many opinions. Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 77–87.'
mla: Cooper, Colin, et al. “Undecided State Dynamics with Many Opinions.” Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, Association
for Computing Machinery, 2026, pp. 77–87, doi:10.1145/3796701.3815920.
short: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga, in:, Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, Association
for Computing Machinery, 2026, pp. 77–87.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2026-07-06
corr_author: '1'
das_tickbox: '1'
date_created: 2026-07-19T22:01:47Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-21T07:54:01Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3796701.3815920
external_id:
arxiv:
- '2603.02636'
file:
- access_level: open_access
checksum: 9ada61feba1e93fd72867a5ba4ee8bb8
content_type: application/pdf
creator: dernst
date_created: 2026-07-21T07:51:58Z
date_updated: 2026-07-21T07:51:58Z
file_id: '22380'
file_name: 2026_ACMPODC_Cooper.pdf
file_size: 709077
relation: main_file
success: 1
file_date_updated: 2026-07-21T07:51:58Z
fulldoi: https://doi.org/10.1145/3796701.3815920
has_accepted_license: '1'
keyword:
- consensus dynamics
- undecided state dynamics
- gossip model
- population protocol model
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77-87
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
Computing
publication_identifier:
isbn:
- '9798400725128'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Undecided state dynamics with many opinions
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: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22327'
abstract:
- lang: eng
text: "Population protocols are a model of distributed computing where\r\n\U0001D45B
agents, each a simple finite-state machine, interact in pairs to\r\nsolve a common
task against a (adversarial) interaction scheduler.\r\nThis model was intensively
studied in recent years; in particular,\r\nthe problem of relative majority received
much attention: Each\r\nagent starts with an input opinion (or color) out of \U0001D458
possibilities,\r\nand the goal is for each agent to eventually output the color
with\r\nthe largest support in the population. Before our work, the state\r\ncomplexity
(the minimum number of states required per agent) was\r\nonly known to be between
Ω(\U0001D458\r\n2\r\n) and\U0001D442(\U0001D458\r\n7\r\n). Our main contribution\r\nis
a population protocol that solves the relative majority problem\r\nwith \U0001D458\r\n3\r\nstates.
We achieve this result with a new protocol called\r\nCircles. While prior approaches
in the literature relied on duels of\r\nagents to find the majority color — an
approach that proved effective\r\nfor the case with two colors — Circles partitions
the agents into\r\ncircular linked lists of decreasing sizes, with the property
that no\r\ntwo agents with the same initial color lie in the same circle. We\r\nshow
that Circles always correctly computes the desired structure\r\nagainst the most
adversarial of schedulers (weakly fair). We then\r\nshow that a trivial extension
of Circles solves the relative majority\r\nproblem. We extend our protocol to
handle various tie-breaking\r\nmechanisms or to support the case where the agents
do not share a\r\nprior ordering of the colors. Finally, we show that a modification
of\r\nCircles solves the ranking problem with 2 · \U0001D458^4\r\nstates, where
each\r\nagent must output the rank of its initial color in the population."
acknowledgement: "Funded by the European union. Views and opinions expressed are\r\nhowever
those of the author(s) only and do not necessarily reflect\r\nthose of the European
Union or the European Research Council\r\nExecutive Agency. Neither the European
Union nor the granting authority can be held responsible for them. This project
has received\r\nfunding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme\r\n(MoDynStruct, No. 101019564)
and the Austrian Science\r\nFund (FWF) grant DOI 10.55776/I5982. For open access
purposes,\r\nthe author has applied a CC BY public copyright license to any\r\nauthor-accepted
manuscript version arising from this submission."
article_processing_charge: Yes
arxiv: 1
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. Ranking opinions with few states
in population protocols. In: Proceedings of the ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2026:414-424.
doi:10.1145/3796701.3815913'
apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2026). Ranking
opinions with few states in population protocols. In Proceedings of the ACM
Symposium on Principles of Distributed Computing (pp. 414–424). Egham, United
Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815913'
chicago: Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid.
“Ranking Opinions with Few States in Population Protocols.” In Proceedings
of the ACM Symposium on Principles of Distributed Computing, 414–24. Association
for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815913.
ieee: T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions
with few states in population protocols,” in Proceedings of the ACM Symposium
on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 414–424.
ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with
few states in population protocols. Proceedings of the ACM Symposium on Principles
of Distributed Computing. PODC: Symposium on Principles of Distributed Computing,
414–424.'
mla: Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population
Protocols.” Proceedings of the ACM Symposium on Principles of Distributed Computing,
Association for Computing Machinery, 2026, pp. 414–24, doi:10.1145/3796701.3815913.
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, 2026, pp. 414–424.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2026-07-06
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-14T05:40:17Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-22T07:49:22Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1145/3796701.3815913
ec_funded: 1
external_id:
arxiv:
- '2605.18707'
file:
- access_level: open_access
checksum: e56da70c1b2e7e663d2d8106cf07a30a
content_type: application/pdf
creator: dernst
date_created: 2026-07-16T11:18:44Z
date_updated: 2026-07-16T11:18:44Z
file_id: '22353'
file_name: 2026_ACMPODC_Breitkopf.pdf
file_size: 702140
relation: main_file
success: 1
file_date_updated: 2026-07-16T11:18:44Z
fulldoi: https://doi.org/10.1145/3796701.3815913
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 414 - 424
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
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9798400725128'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Ranking opinions with few 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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
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-07-24T12:48:29Z
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: '18557'
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
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: '21720'
abstract:
- lang: eng
text: "We present an exact fully-dynamic minimum cut algorithm that runs in \U0001D45B\U0001D45C(1)
deterministic update time when the minimum cut size is at most 2Θ(log3/4−\U0001D450\U0001D45B)
for any \U0001D450 >0, improving on the previous algorithm of Jin, Sun, and Thorup
(SODA 2024) whose minimum cut size limit is (log\U0001D45B)\U0001D45C(1). Combined
with graph sparsification, we obtain the first (1 +\U0001D716)-approximate fully-dynamic
minimum cut algorithm on weighted graphs, for any \U0001D716 ≥2−Θ(log3/4−\U0001D450\U0001D45B),
in \U0001D45B\U0001D45C(1) randomized update time.\r\nOur main technical contribution
is a deterministic local minimum cut algorithm, which replaces the randomized
LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025)."
acknowledgement: Funded by the European union. Views and opinions expressed are however
those of the author(s) only and do not necessarily reflect those of the European
Union or the European Research Council Executive Agency. Neither the European Union
nor the granting authority can be held responsible for them. 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. For open access purposes, the author
has applied a CC BY public copyright license to any author-accepted manuscript version
arising from this submission.
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. Deterministic and exact fully-dynamic minimum
cut of superpolylogarithmic size in subpolynomial time. In: Proceedings of
the Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026. Society for
Industrial and Applied Mathematics; 2026:613-663. doi:10.1137/1.9781611978971.25'
apa: 'El-Hayek, A., Henzinger, M., & Li, J. (2026). Deterministic and exact
fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time.
In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
(Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611978971.25'
chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact
Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.”
In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms,
2026:613–63. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.25.
ieee: A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic
minimum cut of superpolylogarithmic size in subpolynomial time,” in Proceedings
of the Annual ACM SIAM Symposium on Discrete Algorithms, Vancouver, Canada,
2026, vol. 2026, pp. 613–663.
ista: 'El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic
minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of
the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
Algorithms vol. 2026, 613–663.'
mla: El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut
of Superpolylogarithmic Size in Subpolynomial Time.” Proceedings of the Annual
ACM SIAM Symposium on Discrete Algorithms, vol. 2026, Society for Industrial
and Applied Mathematics, 2026, pp. 613–63, doi:10.1137/1.9781611978971.25.
short: A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the Annual ACM SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
2026, pp. 613–663.
conference:
end_date: 2026-01-14
location: Vancouver, Canada
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2026-01-11
date_created: 2026-04-12T22:01:51Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '07'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1137/1.9781611978971.25
ec_funded: 1
external_id:
arxiv:
- '2512.13105'
fulldoi: https://doi.org/10.1137/1.9781611978971.25
intvolume: ' 2026'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2512.13105
month: '01'
oa: 1
oa_version: Preprint
page: 613-663
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
publication: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611978971'
eissn:
- 1557-9468
issn:
- 1071-9040
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size
in subpolynomial time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2026
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22405'
abstract:
- lang: eng
text: "Computing the diameter of the intersection graphs of objects is a basic problem
in computational geometry. Previous works showed that the complexity of computing
the diameter mainly depends on the object types: for unit disks and squares in
2D, the problem is solvable in truly subquadratic time [Chan et al., 2025], while
for other objects, including unit segments and equilateral triangles in 2D or
unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic
time algorithm under the Orthogonal Vector (OV) hypothesis [Bringmann et al.,
2022]. \r\nWe undertake a comprehensive study of computing the diameter of geometric
intersection graphs for various types of objects. We discover many new irregularities,
showing that the landscape is extremely nuanced: the source of hardness is a combination
of the object type, the true diameter value, and how the objects intersect with
each other. Our highlighted results for the 2D case include: \r\n1) The diameter
of non-degenerate, axis-aligned line segments can be computed in truly subquadratic
time. Previous hardness result [Bringmann et al., 2022] for line segments applies
only to degenerate instances. On the other hand, for the degenerate case, we show
that a truly subquadratic time algorithm exists when the true diameter is constant.
\r\n2) An almost-linear-time algorithm for unit-square graphs of constant diameter.
Previous algorithms [Duraj et al., 2024; Chan et al., 2025] rely on succinct representation
assuming bounded VC-dimension; for such a strategy Ω(n^{7/4}) time is an inherent
barrier. \r\n3) An Õ(n^{4/3})-time algorithm to decide if the diameter of a unit-disk
graph is at most 2. This improves upon the recent algorithm with running time
Õ(n^{2-1/9}) [Chan et al., 2025]. \r\n4) Deciding if the diameter of intersection
graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard
under fine-grained complexity assumptions. Previous lower bounds [Bringmann et
al., 2022] only hold when deciding if diameter is at most 3. Our findings are
presented in a pair of papers. This paper focuses solely on the 2D case, while
the companion paper is devoted to higher-dimensional cases."
acknowledgement: "Timothy M. Chan: Supported by NSF grant CCF-2224271.\r\nHsien-Chih
Chang: Supported by NSF CAREER award CCF-2443017.\r\nJie Gao: Supported by NSF DMS-2220271,
DMS-2311064, IIS-2229876, CCF-2118953, CNS-2515159.\r\nSándor Kisfaludi-Bak: Supported
by the Research Council of Finland, Grant 363444.\r\nHung Le: Supported by an NSF
grant CCF-2517033 and an NSF CAREER Award CCF-2237288.\r\nDa Wei Zheng: This project
has received funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982.
For open access purposes, the author has applied a CC BY public copyright\r\nlicense
to any author-accepted manuscript version arising from this submission.\r\n"
article_number: 54:1-54:22
article_processing_charge: No
arxiv: 1
author:
- first_name: Timothy M.
full_name: Chan, Timothy M.
last_name: Chan
orcid: 0000-0002-8093-0675
- first_name: Hsien-Chih
full_name: Chang, Hsien-Chih
last_name: Chang
orcid: 0000-0001-6714-7988
- first_name: Jie
full_name: Gao, Jie
last_name: Gao
orcid: 0000-0001-5083-6082
- first_name: Sándor
full_name: Kisfaludi-Bak, Sándor
last_name: Kisfaludi-Bak
orcid: 0000-0002-6856-2902
- first_name: Hung
full_name: Le, Hung
last_name: Le
orcid: 0000-0001-8223-9944
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. Charting the landscape
of diameter computation on geometric intersection graphs in the plane. In: 53rd
International Colloquium on Automata, Languages, and Programming. Vol 374.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPICS.ICALP.2026.54'
apa: 'Chan, T. M., Chang, H.-C., Gao, J., Kisfaludi-Bak, S., Le, H., & Zheng,
D. W. (2026). Charting the landscape of diameter computation on geometric intersection
graphs in the plane. In 53rd International Colloquium on Automata, Languages,
and Programming (Vol. 374). Egham, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ICALP.2026.54'
chicago: Chan, Timothy M., Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung
Le, and Da Wei Zheng. “Charting the Landscape of Diameter Computation on Geometric
Intersection Graphs in the Plane.” In 53rd International Colloquium on Automata,
Languages, and Programming, Vol. 374. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2026. https://doi.org/10.4230/LIPICS.ICALP.2026.54.
ieee: T. M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, and D. W. Zheng,
“Charting the landscape of diameter computation on geometric intersection graphs
in the plane,” in 53rd International Colloquium on Automata, Languages, and
Programming, Egham, United Kingdom, 2026, vol. 374.
ista: 'Chan TM, Chang H-C, Gao J, Kisfaludi-Bak S, Le H, Zheng DW. 2026. Charting
the landscape of diameter computation on geometric intersection graphs in the
plane. 53rd International Colloquium on Automata, Languages, and Programming.
ICALP: Automata, Languages and Programming vol. 374, 54:1-54:22.'
mla: Chan, Timothy M., et al. “Charting the Landscape of Diameter Computation on
Geometric Intersection Graphs in the Plane.” 53rd International Colloquium
on Automata, Languages, and Programming, vol. 374, 54:1-54:22, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPICS.ICALP.2026.54.
short: T.M. Chan, H.-C. Chang, J. Gao, S. Kisfaludi-Bak, H. Le, D.W. Zheng, in:,
53rd International Colloquium on Automata, Languages, and Programming, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-07-10
location: Egham, United Kingdom
name: 'ICALP: Automata, Languages and Programming'
start_date: 2026-07-07
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-27T05:53:08Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-08-12T09:03:26Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPICS.ICALP.2026.54
external_id:
arxiv:
- '2605.10692'
file:
- access_level: open_access
checksum: 1e66eba4cfe4e74ab28108b1ca0bb956
content_type: application/pdf
creator: dernst
date_created: 2026-07-27T06:20:41Z
date_updated: 2026-07-27T06:20:41Z
file_id: '22407'
file_name: 2026_LIPIcSICALP_Chan.pdf
file_size: 1440497
relation: main_file
success: 1
file_date_updated: 2026-07-27T06:20:41Z
fulldoi: https://doi.org/10.4230/LIPICS.ICALP.2026.54
has_accepted_license: '1'
intvolume: ' 374'
keyword:
- String graphs
- Fine-grained complexity
- Theory of computation → Computational geometry
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 53rd International Colloquium on Automata, Languages, and Programming
publication_identifier:
eissn:
- 1868-8969
- '9783959774284'
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: Charting the landscape of diameter computation on geometric intersection graphs
in the plane
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: 374
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_type: closed access
_id: '22812'
abstract:
- lang: eng
text: Efficient data structures for computing the cutset of a set of nodes in a
graph undergoing dynamic edge insertions/deletions are well-studied in undirected
graphs. We study this problem in directed graphs and show a reduction from the
Online Boolean Matrix-Vector Multiplication Conjecture (OMv) introduced by Henzinger
et al. [STOC’15]. We prove conditional on OMv that a dynamic data structure computing
the directed cutset of a set of nodes cannot have an amortized time of both O(n2−ε)
for a query operation and O(n1−ε) for an update operation, for any constant ε > 0,
even when an adversary’s operations are restricted to the incremental or decremental
settings. We further give algorithms to match these lower bounds.
acknowledgement: This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No. 101034413 and from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) Image
1 dummy alt text. Zofia Stefankovic was partially supported by the ISTernship program
of the Institute of Science and Technology Austria and OEAD.
article_number: '106663'
article_processing_charge: No
article_type: original
author:
- first_name: Niklas
full_name: Hahn, Niklas
id: 0a01c7b2-b823-11ed-9928-cc3f874f9ffd
last_name: Hahn
- 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: Zofia
full_name: Stefankovic, Zofia
last_name: Stefankovic
citation:
ama: Hahn N, Henzinger M, Stefankovic Z. Tight bounds on the performance of dynamic
directed cutset data structures based on OMv. Information Processing Letters.
2026;195. doi:10.1016/j.ipl.2026.106663
apa: Hahn, N., Henzinger, M., & Stefankovic, Z. (2026). Tight bounds on the
performance of dynamic directed cutset data structures based on OMv. Information
Processing Letters. Elsevier. https://doi.org/10.1016/j.ipl.2026.106663
chicago: Hahn, Niklas, Monika Henzinger, and Zofia Stefankovic. “Tight Bounds on
the Performance of Dynamic Directed Cutset Data Structures Based on OMv.” Information
Processing Letters. Elsevier, 2026. https://doi.org/10.1016/j.ipl.2026.106663.
ieee: N. Hahn, M. Henzinger, and Z. Stefankovic, “Tight bounds on the performance
of dynamic directed cutset data structures based on OMv,” Information Processing
Letters, vol. 195. Elsevier, 2026.
ista: Hahn N, Henzinger M, Stefankovic Z. 2026. Tight bounds on the performance
of dynamic directed cutset data structures based on OMv. Information Processing
Letters. 195, 106663.
mla: Hahn, Niklas, et al. “Tight Bounds on the Performance of Dynamic Directed Cutset
Data Structures Based on OMv.” Information Processing Letters, vol. 195,
106663, Elsevier, 2026, doi:10.1016/j.ipl.2026.106663.
short: N. Hahn, M. Henzinger, Z. Stefankovic, Information Processing Letters 195
(2026).
das_tickbox: '1'
dataavailabilitystatement: No data was used for the research described in the article.
date_created: 2026-09-06T22:01:55Z
date_published: 2026-08-30T00:00:00Z
date_updated: 2026-09-09T11:55:47Z
day: '30'
department:
- _id: MoHe
doi: 10.1016/j.ipl.2026.106663
ec_funded: 1
fulldoi: https://doi.org/10.1016/j.ipl.2026.106663
intvolume: ' 195'
keyword:
- Dynamic algorithms
- Graph algorithms
- Directed graphs
- Lower bounds
- Upper bounds
language:
- iso: eng
month: '08'
oa_version: None
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
publication: Information Processing Letters
publication_identifier:
issn:
- 0020-0190
publication_status: epub_ahead
publisher: Elsevier
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Tight bounds on the performance of dynamic directed cutset data structures
based on OMv
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 195
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22146'
abstract:
- lang: eng
text: We study differentially private model training with stochastic gradient descent
under learning rate scheduling and correlated noise. Although correlated noise,
in particular via matrix factorizations, has been shown to improve accuracy, prior
theoretical work focused primarily on the prefix-sum workload. That workload assumes
a constant learning rate, whereas in practice learning rate schedules are widely
used to accelerate training and improve convergence. We close this gap by deriving
general upper and lower bounds for a broad class of learning rate schedules in
both single- and multi-epoch settings. Building on these results, we propose a
learning-rate-aware factorization that achieves improvements over prefix-sum factorizations
under both MaxSE and MeanSE error metrics. Our theoretical analysis yields memory-efficient
constructions suitable for practical deployment, and experiments on CIFAR-10 and
IMDB datasets confirm that schedule-aware factorizations improve accuracy in private
training.
acknowledgement: "We thank Rasmus Pagh, Christoph Lampert and Jalaj Upadhyay for valuable\r\ncomments
on an early draft. We thank Ryan Mckenna for a fruitful discussion on the experiment\r\ndesign.
We thank Antti Honkela for sharing insights on learning rate scheduling and DP.\r\nNikita
P. Kalinin: Funded in part by the Austrian Science Fund (FWF) [10.55776/COE12].\r\nJoel
Daniel Andersson: Funded by the European Union. Views and opinions expressed are
however\r\nthose of the author(s) only and do not necessarily reflect those of the
European Union or the European\r\nResearch Council Executive Agency. Neither the
European Union nor the granting authority can be\r\nheld responsible for them. 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,\r\nNo.
101019564). Additional funding by Providentia, a Data Science Distinguished Investigator
grant\r\nfrom Novo Nordisk Fonden, with additional support from VILLUM Investigator
grant 54451.\r\n"
alternative_title:
- LIPIcs
article_number: 2:1-2:21
article_processing_charge: No
arxiv: 1
author:
- first_name: Nikita
full_name: Kalinin, Nikita
id: 4b14526e-14d2-11ed-ba64-c14c9553d137
last_name: Kalinin
- first_name: Joel D
full_name: Andersson, Joel D
id: 4a893819-d954-11f0-89b1-e360bad9ccc5
last_name: Andersson
citation:
ama: 'Kalinin N, Andersson JD. Learning rate scheduling with matrix factorization
for private training. In: 7th Symposium on Foundations of Responsible Computing.
Vol 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.FORC.2026.2'
apa: 'Kalinin, N., & Andersson, J. D. (2026). Learning rate scheduling with
matrix factorization for private training. In 7th Symposium on Foundations
of Responsible Computing (Vol. 368). Cambridge, MA; United States: Schloss
Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.FORC.2026.2'
chicago: Kalinin, Nikita, and Joel D Andersson. “Learning Rate Scheduling with Matrix
Factorization for Private Training.” In 7th Symposium on Foundations of Responsible
Computing, Vol. 368. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
https://doi.org/10.4230/LIPIcs.FORC.2026.2.
ieee: N. Kalinin and J. D. Andersson, “Learning rate scheduling with matrix factorization
for private training,” in 7th Symposium on Foundations of Responsible Computing,
Cambridge, MA; United States, 2026, vol. 368.
ista: 'Kalinin N, Andersson JD. 2026. Learning rate scheduling with matrix factorization
for private training. 7th Symposium on Foundations of Responsible Computing. FORC:
Symposium on Foundations of Responsible Computing, LIPIcs, vol. 368, 2:1-2:21.'
mla: Kalinin, Nikita, and Joel D. Andersson. “Learning Rate Scheduling with Matrix
Factorization for Private Training.” 7th Symposium on Foundations of Responsible
Computing, vol. 368, 2:1-2:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026, doi:10.4230/LIPIcs.FORC.2026.2.
short: N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible
Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-06-05
location: Cambridge, MA; United States
name: 'FORC: Symposium on Foundations of Responsible Computing'
start_date: 2026-06-03
corr_author: '1'
das_tickbox: '0'
date_created: 2026-06-28T22:01:34Z
date_published: 2026-06-01T00:00:00Z
date_updated: 2026-09-16T07:37:21Z
day: '01'
ddc:
- '000'
department:
- _id: ChLa
- _id: GradSch
- _id: MoHe
doi: 10.4230/LIPIcs.FORC.2026.2
ec_funded: 1
external_id:
arxiv:
- '2511.17994'
file:
- access_level: open_access
checksum: c661f016d3861a1c1b590b87a744d087
content_type: application/pdf
creator: dernst
date_created: 2026-06-29T06:55:23Z
date_updated: 2026-06-29T06:55:23Z
file_id: '22149'
file_name: 2026_LIPIcsFORC_Kalinin.pdf
file_size: 1231914
relation: main_file
success: 1
file_date_updated: 2026-06-29T06:55:23Z
fulldoi: https://doi.org/10.4230/LIPIcs.FORC.2026.2
has_accepted_license: '1'
intvolume: ' 368'
keyword:
- differential privacy
- machine learning
- matrix factorization
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: d8f03aaa-b035-11f1-8588-d5147fa879e0
grant_number: COE12
name: Bilateral Artificial Intelligence (Lampert)
publication: 7th Symposium on Foundations of Responsible Computing
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774192'
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: Learning rate scheduling with matrix factorization for private training
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: 368
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22916'
abstract:
- lang: eng
text: "In the imprecise geometry model, the input is a family of regions F = (R₁,
R₂, …,R_n), each containing a point p_i ∈ R_i. The task is then to compute some
function of the points p₁,p₂,… p_n, in our case an implicit representation of
their Pareto front. To this end, one may query a region R_i to retrieve its contained
point p_i ∈ R_i. In this model, efficiency is interpreted in two ways: minimizing
(i) the number of retrievals, and (ii) the computation time both for preprocessing,
and the execution of the query stage, i.e. for computing which points to query
and constructing the output. \r\nWe present an algorithm to construct (an implicit
representation of) the Pareto front for possibly overlapping rectangles, that
is instance-optimal with respect to the number of retrievals. This means that
for every fixed input (F, P), there is no algorithm that retrieves asymptotically
fewer regions to compute the output. This is a strong algorithmic quality, as
it means that our algorithm is competitive even to clairvoyant algorithms which
only have to verify the correctness of a correct guess. In terms of algorithmic
running time, instance-optimality is provably unobtainable. We instead present
an algorithm which is within a log n-factor of instance optimality. This generalizes
earlier results which assumed the regions to not overlap, at only a minor cost
in running time. \r\nFor unit squares, we present an algorithm that is not only
instance optimal in the number of retrievals, but also universally optimal in
terms of running time. This means that for any fixed set of regions F, no algorithm
has a better worst-case running time for all possible point sets P. Thus, this
work presents the first universally optimal algorithm for overlapping planar input.
Compared to previous work, our result improves the degree to which the input regions
may overlap, the preprocessing time, the number of retrievals, and the running
time."
acknowledgement: This work was supported by the the VILLUM Foundation grant (VIL37507)
"Efficient Recomputations for Changeful Problems".
alternative_title:
- LIPIcs
article_number: '106'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sarita
full_name: De Berg, Sarita
last_name: De Berg
- first_name: Nynne Maria Foldager
full_name: Bække, Nynne Maria Foldager
last_name: Bække
- first_name: Frida Astrup
full_name: Eriksen, Frida Astrup
last_name: Eriksen
- first_name: Ivor
full_name: Van Der Hoog, Ivor
last_name: Van Der Hoog
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Daniel P
full_name: Rutschmann, Daniel P
id: 7397d908-b582-11f0-bf73-88b902e86527
last_name: Rutschmann
citation:
ama: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
DP. Instance optimal and universally optimal bounds for imprecise pareto fronts.
In: 34th Annual European Symposium on Algorithms. Vol 388. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.106'
apa: 'De Berg, S., Bække, N. M. F., Eriksen, F. A., Van Der Hoog, I., Rotenberg,
E., & Rutschmann, D. P. (2026). Instance optimal and universally optimal bounds
for imprecise pareto fronts. In 34th Annual European Symposium on Algorithms
(Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ESA.2026.106'
chicago: De Berg, Sarita, Nynne Maria Foldager Bække, Frida Astrup Eriksen, Ivor
Van Der Hoog, Eva Rotenberg, and Daniel P Rutschmann. “Instance Optimal and Universally
Optimal Bounds for Imprecise Pareto Fronts.” In 34th Annual European Symposium
on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026. https://doi.org/10.4230/LIPIcs.ESA.2026.106.
ieee: S. De Berg, N. M. F. Bække, F. A. Eriksen, I. Van Der Hoog, E. Rotenberg,
and D. P. Rutschmann, “Instance optimal and universally optimal bounds for imprecise
pareto fronts,” in 34th Annual European Symposium on Algorithms, L’Aquila,
Italy, 2026, vol. 388.
ista: 'De Berg S, Bække NMF, Eriksen FA, Van Der Hoog I, Rotenberg E, Rutschmann
DP. 2026. Instance optimal and universally optimal bounds for imprecise pareto
fronts. 34th Annual European Symposium on Algorithms. ESA: European Symposium
on Algorithms, LIPIcs, vol. 388, 106.'
mla: De Berg, Sarita, et al. “Instance Optimal and Universally Optimal Bounds for
Imprecise Pareto Fronts.” 34th Annual European Symposium on Algorithms,
vol. 388, 106, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.106.
short: S. De Berg, N.M.F. Bække, F.A. Eriksen, I. Van Der Hoog, E. Rotenberg, D.P.
Rutschmann, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T08:59:49Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.106
external_id:
arxiv:
- '2605.07523'
file:
- access_level: open_access
checksum: 75cfae9e9773be4b06f9aab66041f0f3
content_type: application/pdf
creator: dernst
date_created: 2026-09-16T08:58:04Z
date_updated: 2026-09-16T08:58:04Z
file_id: '22935'
file_name: 2026_LIPIcsESA_deBerg.pdf
file_size: 1102214
relation: main_file
success: 1
file_date_updated: 2026-09-16T08:58:04Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.106
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Pareto front
- imprecise geometry
- instance optimality
- universal optimality
- preprocessing model
- partial information
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959774451'
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: Instance optimal and universally optimal bounds for imprecise pareto fronts
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: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22915'
abstract:
- lang: eng
text: "The element distinctness problem takes as input a list I of n values from
a totally ordered universe, where pairwise comparisons between values are allowed,
and the goal is to decide whether I contains any duplicates. It is a well-studied
problem with a classical worst-case Ω(n log n) comparison-based lower bound by
Fredman [TCS'76]. At first glance, this lower bound appears to rule out any algorithm
more efficient than the naive approach of sorting I and comparing adjacent elements.
However, upon closer inspection, the Ω(n log n) bound is overly pessimistic. For
instance, if I contains n/2 identical elements, a median-finding algorithm will,
regardless of the input order, find a duplicate in linear time. This raises a
natural question: Are there comparison-based lower bounds for element distinctness
that are sensitive to the amount of duplicates in the input instance?\r\nTo address
this question, we derive instance-specific lower bounds. For any input instance
I, we represent the combinatorial structure of the duplicates in I by an undirected
graph G(I) that connects identical elements. Each such graph G is a union of cliques,
and we study algorithms by their worst-case running time over all inputs I' with
G(I') ≅ G. We establish an adversarial lower bound showing that, for any deterministic
algorithm \U0001D49C, there exists a graph G and an algorithm \U0001D49C' that,
for all inputs I with G(I) ≅ G, is a factor O(log log n) faster than \U0001D49C.
Consequently, no deterministic algorithm can be o(log log n)-competitive for all
graphs G. We complement this with an O(log log n)-competitive deterministic algorithm,
thereby obtaining tight bounds for element distinctness that go beyond classical
worst-case analysis. Subsequently, we study the related problem of set intersection.
We show that no deterministic set intersection algorithm can be o(log n)-competitive,
and provide an O(log n)-competitive deterministic algorithm. We find it interesting
and surprising to discover tight O(log log n)-competitive bounds for element distinctness.
Moreover, we find the separation between element distinctness and the set intersection
problem unexpected."
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
programme (No. 101019564) "
alternative_title:
- LIPIcs
article_number: '101'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
full_name: Van Der Hoog, Ivor
last_name: Van Der Hoog
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Daniel P
full_name: Rutschmann, Daniel P
id: 7397d908-b582-11f0-bf73-88b902e86527
last_name: Rutschmann
citation:
ama: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. Tight Better-Than-Worst-Case bounds
for element distinctness and set intersection. In: 34th Annual European Symposium
on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2026. doi:10.4230/LIPIcs.ESA.2026.101'
apa: 'Van Der Hoog, I., Rotenberg, E., & Rutschmann, D. P. (2026). Tight Better-Than-Worst-Case
bounds for element distinctness and set intersection. In 34th Annual European
Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.101'
chicago: Van Der Hoog, Ivor, Eva Rotenberg, and Daniel P Rutschmann. “Tight Better-Than-Worst-Case
Bounds for Element Distinctness and Set Intersection.” In 34th Annual European
Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.101.
ieee: I. Van Der Hoog, E. Rotenberg, and D. P. Rutschmann, “Tight Better-Than-Worst-Case
bounds for element distinctness and set intersection,” in 34th Annual European
Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.
ista: 'Van Der Hoog I, Rotenberg E, Rutschmann DP. 2026. Tight Better-Than-Worst-Case
bounds for element distinctness and set intersection. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 101.'
mla: Van Der Hoog, Ivor, et al. “Tight Better-Than-Worst-Case Bounds for Element
Distinctness and Set Intersection.” 34th Annual European Symposium on Algorithms,
vol. 388, 101, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.101.
short: I. Van Der Hoog, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual European
Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-16T09:21:35Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.101
ec_funded: 1
external_id:
arxiv:
- '2511.02954'
file:
- access_level: open_access
checksum: c552853bfa37e4b9a0f060107e464ed0
content_type: application/pdf
creator: dernst
date_created: 2026-09-16T09:20:49Z
date_updated: 2026-09-16T09:20:49Z
file_id: '22937'
file_name: 2026_LIPIcsESA_vanderHoog.pdf
file_size: 892322
relation: main_file
success: 1
file_date_updated: 2026-09-16T09:20:49Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.101
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Comparison-based analysis
- set intersection
- universal optimality
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
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959774451'
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: yes
title: Tight Better-Than-Worst-Case bounds for element distinctness and set intersection
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: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22914'
abstract:
- lang: eng
text: "We present the first truly subquadratic time algorithm to compute diameter
and eccentricities in real-weighted directed graphs with constant distance VC-dimension
and strongly sublinear-sized balanced separators. For real-weighted K_h-minor-free
digraphs, this runs in O(n^{2-1/(2h-2)} polylog(n)) time.\r\nPrior to this work,
truly subquadratic time computation of diameter was only known for real-weighted
planar graphs, while extensions to broader classes like minor-free graphs were
restricted to unweighted settings. In particular, existing algorithms that use
VC-dimension [Ducoffe, Habib, Viennot; SICOMP 2022] [Le, Wulff-Nilsen; SODA 2024]
[Chan, Chang, Gao, Le, Kisfaludi-Bak, Zheng; FOCS 2025] work with small integer
weights, but do not naturally generalize to real weights. We overcome this barrier
by introducing a randomized search-to-decision reduction, demonstrating that VC-dimension
is a sufficiently powerful tool in the real-weighted regime."
acknowledgement: "This project has received funding from the Austrian Science Fund
(FWF)\r\ngrant DOI 10.55776/I5982. For open access purposes, the author has applied
a CC BY public\r\ncopyright license to any author-accepted manuscript version arising
from this submission. Thanks to Jie Gao for feedback on a preliminary version of
the manuscript"
alternative_title:
- LIPIcs
article_number: 61:1-61:12
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Zheng DW. Real-weighted diameter and eccentricities of minor-free and bounded
VC-dimension graphs in truly subquadratic time. In: 34th Annual European Symposium
on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2026. doi:10.4230/LIPIcs.ESA.2026.61'
apa: 'Zheng, D. W. (2026). Real-weighted diameter and eccentricities of minor-free
and bounded VC-dimension graphs in truly subquadratic time. In 34th Annual
European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.61'
chicago: Zheng, Da Wei. “Real-Weighted Diameter and Eccentricities of Minor-Free
and Bounded VC-Dimension Graphs in Truly Subquadratic Time.” In 34th Annual
European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.61.
ieee: D. W. Zheng, “Real-weighted diameter and eccentricities of minor-free and
bounded VC-dimension graphs in truly subquadratic time,” in 34th Annual European
Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.
ista: 'Zheng DW. 2026. Real-weighted diameter and eccentricities of minor-free and
bounded VC-dimension graphs in truly subquadratic time. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 61:1-61:12.'
mla: Zheng, Da Wei. “Real-Weighted Diameter and Eccentricities of Minor-Free and
Bounded VC-Dimension Graphs in Truly Subquadratic Time.” 34th Annual European
Symposium on Algorithms, vol. 388, 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.61.
short: D.W. Zheng, in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:52Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T09:31:02Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.61
external_id:
arxiv:
- '2607.01926'
file:
- access_level: open_access
checksum: 574f50435b092a72041c7365cac3d280
content_type: application/pdf
creator: dernst
date_created: 2026-09-17T09:28:04Z
date_updated: 2026-09-17T09:28:04Z
file_id: '22942'
file_name: 2026_LIPIcsESA_Zheng.pdf
file_size: 760002
relation: main_file
success: 1
file_date_updated: 2026-09-17T09:28:04Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.61
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Diameter
- eccentricities
- minor-free graphs
- real weights
- VC-dimension
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774451'
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: Real-weighted diameter and eccentricities of minor-free and bounded VC-dimension
graphs in truly subquadratic 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22918'
abstract:
- lang: eng
text: "Given a weighted digraph G, a (t,g,μ)-DAG cover is a collection of g dominating
DAGs D_1,… ,D_g such that all distances are approximately preserved: for every
pair (u,v) of vertices, min_id_{D_i}(u,v) ≤ t⋅ d_G(u,v), and the total number
of non-G edges is bounded by |(∪_i D_i)⧵ G| ≤ μ. Assadi, Hoppenworth, and Wein
[STOC 25] and Filtser [SODA 26] studied DAG covers for general digraphs. This
paper initiates the study of Steiner DAG cover, where the DAGs are allowed to
contain Steiner points. \r\nWe obtain Steiner DAG covers on the important classes
of planar digraphs and low-treewidth digraphs. Specifically, we show that any
digraph with treewidth tw admits a (1,2,Õ(n⋅tw))-Steiner DAG cover. For planar
digraphs we provide a (1+ε,2,Õ_ε(n))-Steiner DAG cover.\r\nWe also demonstrate
a stark difference between Steiner and non-Steiner DAG covers. As a lower bound,
we show that any non-Steiner DAG cover for graphs with treewidth 1 with stretch
t < 2 and sub-quadratic number of extra edges requires Ω(log n) DAGs."
acknowledgement: "This work was initiated at Dagstuhl Seminar 25212: Metric Sketching
and\r\nDynamic Algorithms for Geometric and Topological Graphs. We thank the organizers
and other\r\nparticipants for a productive environment.\r\nujoy Bhore: Work supported
in part by ANRF ARG-MATRICS, Grant 002465.\r\nHsien-Chih Chang: Supported by the
U.S. National Science Foundation Grant No. CCF-2443017.\r\nJonathan Conroy: Supported
by the U.S. National Science Foundation Grant No. CCF-2443017.\r\nArnold Filtser:
This research was supported by the ISRAEL SCIENCE FOUNDATION (grant No.\r\n1042/22).\r\nEunjin
Oh: Supported by Institute of Information & Communications Technology Planning &\r\nEvaluation
(IITP) grant funded by the Korea government (MSIT) (No. RS-2024-00440239, Sublinear\r\nScalable
Algorithms for Large-Scale Data Analysis) and the National Research Foundation of
Korea\r\n(NRF) grant funded by the Korea government (MSIT) (No. RS-2024-00358505).\r\nNicole
Wein: Supported by NSF CAREER award 2541910.\r\nDa Wei Zheng: This project has received
funding from the Austrian Science Fund (FWF) grant\r\nDOI 10.55776/I5982. For open
access purposes, the author has applied a CC BY public copyright\r\nlicense to any
author-accepted manuscript version arising from this submission."
alternative_title:
- LIPIcs
article_number: 94:1-94:18
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Sujoy
full_name: Bhore, Sujoy
last_name: Bhore
- first_name: Hsien Chih
full_name: Chang, Hsien Chih
last_name: Chang
- first_name: Jonathan
full_name: Conroy, Jonathan
last_name: Conroy
- first_name: Arnold
full_name: Filtser, Arnold
last_name: Filtser
- first_name: Eunjin
full_name: Oh, Eunjin
last_name: Oh
- first_name: Nicole
full_name: Wein, Nicole
last_name: Wein
- first_name: Da Wei
full_name: Zheng, Da Wei
id: af77956b-e859-11ef-8dc9-d301b898e32f
last_name: Zheng
citation:
ama: 'Bhore S, Chang HC, Conroy J, et al. DAG covers for structured graphs: The
Steiner point effect. In: 34th Annual European Symposium on Algorithms.
Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2026. doi:10.4230/LIPIcs.ESA.2026.94'
apa: 'Bhore, S., Chang, H. C., Conroy, J., Filtser, A., Oh, E., Wein, N., &
Zheng, D. W. (2026). DAG covers for structured graphs: The Steiner point effect.
In 34th Annual European Symposium on Algorithms (Vol. 388). L’Aquila, Italy:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.94'
chicago: 'Bhore, Sujoy, Hsien Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin
Oh, Nicole Wein, and Da Wei Zheng. “DAG Covers for Structured Graphs: The Steiner
Point Effect.” In 34th Annual European Symposium on Algorithms, Vol. 388.
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.94.'
ieee: 'S. Bhore et al., “DAG covers for structured graphs: The Steiner point
effect,” in 34th Annual European Symposium on Algorithms, L’Aquila, Italy,
2026, vol. 388.'
ista: 'Bhore S, Chang HC, Conroy J, Filtser A, Oh E, Wein N, Zheng DW. 2026. DAG
covers for structured graphs: The Steiner point effect. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 94:1-94:18.'
mla: 'Bhore, Sujoy, et al. “DAG Covers for Structured Graphs: The Steiner Point
Effect.” 34th Annual European Symposium on Algorithms, vol. 388, 94:1-94:18,
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.94.'
short: S. Bhore, H.C. Chang, J. Conroy, A. Filtser, E. Oh, N. Wein, D.W. Zheng,
in:, 34th Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:27:46Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.94
external_id:
arxiv:
- '2604.04186'
file:
- access_level: open_access
checksum: 2082683b3b72865c6a795305e5d61276
content_type: application/pdf
creator: dernst
date_created: 2026-09-17T10:09:22Z
date_updated: 2026-09-17T10:09:22Z
file_id: '22948'
file_name: 2026_LIPIcsESA_Bhore.pdf
file_size: 1123327
relation: main_file
success: 1
file_date_updated: 2026-09-17T10:09:22Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.94
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Directed graphs
- DAG (directed acyclic graphs)
- distortion
- metric embeddings
- planar graph
- treewidth
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
isbn:
- '9783959774451'
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: yes
title: 'DAG covers for structured graphs: The Steiner point effect'
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: 388
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '22917'
abstract:
- lang: eng
text: 'A heap is a dynamic data structure that stores a set of labeled values under
the following operations: pop returns the minimum value of the heap, Push(x_i)
pushes a new value x_i onto the heap, and DecreaseKey(i, v) decreases the value
x_i to v. A working-set heap is a heap that supports the x_i ← pop() operation
in O(log Γ(x_i)) time where Γ(x_i) is the size of the working set: the number
of elements that were pushed onto the heap while x_i was in the heap. The goal
of working set heap design is to maintain the working set property while minimizing
the overhead of the Push and DecreaseKey operations. On a word RAM, there exist
working set heaps that support Push and DecreaseKey in amortized constant time.
In this paper, we show via a simple construction that pointer machines, one of
the most general and least-assuming computational models, support working set
heaps that support Push in amortized constant time and DecreaseKey in inverse-Ackermann
time. A by-product of this analysis is that Dijkstra’s shortest path algorithm
can be near-universally optimal on a pointer machine - incurring only an additive
O(m α(m)) overhead compared to the optimal running time for distance ordering,
where m denotes the number of edges in the graph.'
acknowledgement: "Ivor van der Hoog, Eva Rotenberg, and Daniel Rutschmann thank the
VILLUM Foundation\r\ngrant (VIL37507) “Efficient Recomputations for Changeful Problems”
for supporting this work.\r\nDaniel Rutschmann is supported by the European Research
Council (ERC) under the European\r\nUnion’s Horizon 2020 research and innovation
programme (No. 101019564) . John Iacono\r\nis supported by the Fonds de la Recherche
Scientifique – FNRS.This work started at Dagstuhl 25191: Adaptive and Scalable Data
Structures.\r\n\r\n"
alternative_title:
- LIPIcs
article_number: 45:1-45:13
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Ivor
full_name: Van Der Hoog, Ivor
last_name: Van Der Hoog
- first_name: John
full_name: Iacono, John
last_name: Iacono
- first_name: Eva
full_name: Rotenberg, Eva
last_name: Rotenberg
- first_name: Daniel P
full_name: Rutschmann, Daniel P
id: 7397d908-b582-11f0-bf73-88b902e86527
last_name: Rutschmann
citation:
ama: 'Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. Near-optimal working-set
heaps and dijkstra on pointer machines. In: 34th Annual European Symposium
on Algorithms. Vol 388. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2026. doi:10.4230/LIPIcs.ESA.2026.45'
apa: 'Van Der Hoog, I., Iacono, J., Rotenberg, E., & Rutschmann, D. P. (2026).
Near-optimal working-set heaps and dijkstra on pointer machines. In 34th Annual
European Symposium on Algorithms (Vol. 388). L’Aquila, Italy: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2026.45'
chicago: Van Der Hoog, Ivor, John Iacono, Eva Rotenberg, and Daniel P Rutschmann.
“Near-Optimal Working-Set Heaps and Dijkstra on Pointer Machines.” In 34th
Annual European Symposium on Algorithms, Vol. 388. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2026. https://doi.org/10.4230/LIPIcs.ESA.2026.45.
ieee: I. Van Der Hoog, J. Iacono, E. Rotenberg, and D. P. Rutschmann, “Near-optimal
working-set heaps and dijkstra on pointer machines,” in 34th Annual European
Symposium on Algorithms, L’Aquila, Italy, 2026, vol. 388.
ista: 'Van Der Hoog I, Iacono J, Rotenberg E, Rutschmann DP. 2026. Near-optimal
working-set heaps and dijkstra on pointer machines. 34th Annual European Symposium
on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 388, 45:1-45:13.'
mla: Van Der Hoog, Ivor, et al. “Near-Optimal Working-Set Heaps and Dijkstra on
Pointer Machines.” 34th Annual European Symposium on Algorithms, vol. 388,
45:1-45:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, doi:10.4230/LIPIcs.ESA.2026.45.
short: I. Van Der Hoog, J. Iacono, E. Rotenberg, D.P. Rutschmann, in:, 34th Annual
European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2026.
conference:
end_date: 2026-09-04
location: L’Aquila, Italy
name: 'ESA: European Symposium on Algorithms'
start_date: 2026-08-31
corr_author: '1'
das_tickbox: '0'
date_created: 2026-09-13T22:01:53Z
date_published: 2026-08-25T00:00:00Z
date_updated: 2026-09-17T10:35:56Z
day: '25'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ESA.2026.45
ec_funded: 1
external_id:
arxiv:
- '2604.24134'
file:
- access_level: open_access
checksum: 52e7cb8881060e8f17b89cd46504f445
content_type: application/pdf
creator: dernst
date_created: 2026-09-17T10:33:12Z
date_updated: 2026-09-17T10:33:12Z
file_id: '22949'
file_name: 2026_LIPIcsESA_vanderHoog2.pdf
file_size: 792024
relation: main_file
success: 1
file_date_updated: 2026-09-17T10:33:12Z
fulldoi: https://doi.org/10.4230/LIPIcs.ESA.2026.45
has_accepted_license: '1'
intvolume: ' 388'
keyword:
- Data structures
- graph algorithms
- amortized analysis
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
publication: 34th Annual European Symposium on Algorithms
publication_identifier:
eissn:
- 1868-8969
isbn:
- '9783959774451'
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: Near-optimal working-set heaps and dijkstra on pointer machines
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: 388
year: '2026'
...