Please note that LibreCat no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
39 Publications
2026 |
Published |
Journal Article |
IST-REx-ID: 21159 |
| 
|
Counting perfect matchings in Dirac hypergraphs
M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).
[Published Version]
View
| Files available
| DOI
| arXiv
M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).
2025 |
Published |
Conference Paper |
IST-REx-ID: 19858 |
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
A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
2025 |
Published |
Conference Paper |
IST-REx-ID: 19982 |
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
| DOI
| Download Preprint (ext.)
| arXiv
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.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20051 |
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
A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20052 |
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
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.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20301 |
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
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.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20533 |
Securing dynamic data: A primer on differentially private data structures
M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[Published Version]
View
| Files available
| DOI
M. Henzinger, R. Safavi Hemami, in:, 33rd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20534 |
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
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.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20535 |
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
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.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20536 |
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
R. Safavi Hemami, M.P. Seybold, in:, 19th International Symposium on Algorithms and Data Structures, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
2025 |
Published |
Conference Paper |
IST-REx-ID: 20819 |
Differentially private federated k-means clustering with server-side data
J.A. Scott, C. Lampert, D. Saulpic, in:, 42nd International Conference on Machine Learning, ML Research Press, 2025, pp. 53757–53790.
[Published Version]
View
| Files available
| arXiv
J.A. Scott, C. Lampert, D. Saulpic, in:, 42nd International Conference on Machine Learning, ML Research Press, 2025, pp. 53757–53790.
2025 |
Published |
Conference Paper |
IST-REx-ID: 19038 |
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
M. Henzinger, J. Upadhyay, in:, Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, 2025, pp. 2951–2970.
2025 |
Published |
Journal Article |
IST-REx-ID: 15121 |
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
D.W. Zheng, M. Henzinger, Mathematical Programming 210 (2025) 881–894.
2025 |
Published |
Conference Paper |
IST-REx-ID: 21280 |
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
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.
2024 |
Published |
Conference Paper |
IST-REx-ID: 18115 |
Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond
K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic, D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 2086–2107.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
K. Axiotis, V. Cohen-Addad, M. Henzinger, S. Jerome, V. Mirrokni, D. Saulpic, D.P. Woodruff, M. Wunder, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 2086–2107.
2024 |
Published |
Conference Paper |
IST-REx-ID: 18116 |
Making old things new: A unified algorithm for differentially private clustering
M.D. La Tour, M. Henzinger, D. Saulpic, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 12046–12086.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
M.D. La Tour, M. Henzinger, D. Saulpic, in:, Proceedings of the 41st International Conference on Machine Learning, ML Research Press, 2024, pp. 12046–12086.
2024 |
Published |
Conference Paper |
IST-REx-ID: 18156 |
Private counting of distinct elements in the turnstile model and extensions
M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version]
View
| Files available
| DOI
| WoS
| arXiv
M. Henzinger, A.R. Sricharan, T.A. Steiner, in:, International Conference on Approximation Algorithms for Combinatorial Optimization Problems , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
2024 |
Published |
Conference Paper |
IST-REx-ID: 18308 |
Fully dynamic k-means coreset in near-optimal update time
M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version]
View
| Files available
| DOI
| WoS
| arXiv
M.D. La Tour, M. Henzinger, D. Saulpic, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
2024 |
Published |
Conference Paper |
IST-REx-ID: 18309 |
Connectivity oracles for predictable vertex failures
B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version]
View
| Files available
| DOI
| WoS
| arXiv
B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
2024 |
Published |
Conference Paper |
IST-REx-ID: 18503 |
Deterministic near-linear time minimum cut in weighted graphs
M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–3139.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
M. Henzinger, J. Li, S. Rao, D. Wang, in:, 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–3139.