The design and evaluation of modern fully dynamic data structures

Project Period: 2023-03-01 – 2026-12-31
Funder: European Research Council
Acronym
MoDynStruct
Principal Investigator
Department(s)
Henzinger_Monika Group
Grant Number
101019564
Grant DOI
10.3030/101019564
Funder
European Research Council
Funder Schema
H2020-ERC-AdG
Funder Registry
10.13039/501100000781

41 Publications

2026 | Published | Conference Paper | IST-REx-ID: 21719 | OA
Dynamic hierarchical j-tree decomposition and its applications
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.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 22146 | OA
Learning rate scheduling with matrix factorization for private training
N. Kalinin, J.D. Andersson, in:, 7th Symposium on Foundations of Responsible Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 22245 | OA
An improved quality hierarchical congestion approximator in near-linear time
M. Henzinger, R. Münk, H. Räcke, in:, 58th Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 2026, pp. 1417–1428.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Journal Article | IST-REx-ID: 22318 | OA | PlanS
Concurrent composition for differentially private continual mechanisms
M. Henzinger, R. Safavi Hemami, S. Vadhan, Proceedings of the ACM on Management of Data 4 (2026) 1–26.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Journal Article | IST-REx-ID: 22322 | OA | PlanS
Improved lower bounds for privacy under continual release
B. Aryanfard, M. Henzinger, D. Saulpic, A.R. Sricharan, Proceedings of the ACM on Management of Data 4 (2026) 1–27.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Conference Paper | IST-REx-ID: 22327 | OA
Ranking opinions with few states in population protocols
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.
[Published Version] View | Files available | DOI | arXiv
 
2026 | Published | Thesis | PhD | IST-REx-ID: 22281 | OA
Handling updates and failures: Dynamic graph algorithms and distributed computing on dynamic networks
A. El-Hayek, Handling Updates and Failures: Dynamic Graph Algorithms and Distributed Computing on Dynamic Networks, Institute of Science and Technology Austria, 2026.
[Published Version] View | Files available | DOI
 
2026 | Published | Conference Paper | IST-REx-ID: 21720 | OA
Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time
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.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 21280 | OA
Incremental approximate maximum flow via residual graph sparsification
G. Goranci, M. Henzinger, H. Räcke, A. Sricharan, in:, 52nd International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, p. 91:1-91:20.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Journal Article | IST-REx-ID: 15121 | OA
Multiplicative auction algorithm for approximate maximum weight bipartite matching
D.W. Zheng, M. Henzinger, Mathematical Programming 210 (2025) 881–894.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | WoS | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 19038 | OA
Improved differentially private continual observation using group algebra
M. Henzinger, J. Upadhyay, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, 2025, pp. 2951–2970.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 19858 | OA
On b-matching and fully-dynamic maximum k-edge coloring
A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | WoS | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20052 | OA
Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols
T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 549–552.
[Published Version] View | Files available | DOI | WoS
 
2025 | Published | Conference Paper | IST-REx-ID: 20301 | OA
Differentially private continual release of histograms and related queries
M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, The 28th International Conference on Artificial Intelligence and Statistics, ML Research Press, 2025, pp. 1990–1998.
[Preprint] View | Download Preprint (ext.) | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20534 | OA
Efficient contractions of dynamic graphs - with applications
M. Henzinger, E. Kosinas, R. Münk, H. Räcke, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20535 | OA
Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism
L. Dhulipala, M. Henzinger, G.Z. Li, Q.C. Liu, A.R. Sricharan, L. Zhu, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20536 | OA
B-Treaps revised: Write efficient randomized block search trees with high load
R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version] View | Files available | DOI | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 20051 | OA
An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model
A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025.
[Published Version] View | Files available | DOI | WoS | arXiv
 
2025 | Published | Conference Paper | IST-REx-ID: 19982 | OA
Fully dynamic approximate minimum cut in subpolynomial time per operation
A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–784.
[Preprint] View | Files available | DOI | Download Preprint (ext.) | arXiv
 
2024 | Published | Conference Paper | IST-REx-ID: 14769 | OA
Experimental evaluation of fully dynamic k-means via coresets
M. Henzinger, D. Saulpic, L. Sidl, in:, 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–233.
[Preprint] View | DOI | Download Preprint (ext.) | arXiv
 

Search

Filter Publications

Display / Sort

Export / Embed