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.
29 Publications
2025 | Published | Conference Paper | IST-REx-ID: 19038 | 
Henzinger M, Upadhyay J. Improved differentially private continual observation using group algebra. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 5. Association for Computing Machinery; 2025:2951-2970. doi:10.1137/1.9781611978322.95
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2025 | Published | Journal Article | IST-REx-ID: 15121 |
Zheng DW, Henzinger M. Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. 2025;210:881-894. doi:10.1007/s10107-024-02066-3
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 19858 |
El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum k-edge coloring. In: 4th Symposium on Algorithmic Foundations of Dynamic Networks. Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SAND.2025.4
[Published Version]
View
| Files available
| DOI
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20051 |
El-Hayek A, Elsässer R, Schmid S. An almost tight lower bound for plurality consensus with undecided state dynamics in the population protocol model. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery; 2025. doi:10.1145/3732772.3733505
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18309 |
Hu B, Kosinas E, Polak A. Connectivity oracles for predictable vertex failures. In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.72
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Journal Article | IST-REx-ID: 17188 |
Braun P, Hahn N, Hoefer M, Schecker C. Delegated online search. Artificial Intelligence. 2024;334. doi:10.1016/j.artint.2024.104171
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18557 |
El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In: 38th International Symposium on Distributed Computing. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.DISC.2024.21
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18156 |
Henzinger M, Sricharan AR, Steiner TA. Private counting of distinct elements in the turnstile model and extensions. In: International Conference on Approximation Algorithms for Combinatorial Optimization Problems . Vol 317. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.APPROX/RANDOM.2024.40
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18308 |
La Tour MD, Henzinger M, Saulpic D. Fully dynamic k-means coreset in near-optimal update time. In: 32nd Annual European Symposium on Algorithms. Vol 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ESA.2024.100
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18115 |
Axiotis K, Cohen-Addad V, Henzinger M, et al. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In: Proceedings of the 41st International Conference on Machine Learning. Vol 235. ML Research Press; 2024:2086-2107.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15253 |
Henzinger M, Upadhyay J, Upadhyay S. A unifying framework for differentially private sums under continual observation. In: Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms. Vol 2024. Society for Industrial and Applied Mathematics; 2024:995-1018. doi:10.1137/1.9781611977912.38
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 14769 |
Henzinger M, Saulpic D, Sidl L. Experimental evaluation of fully dynamic k-means via coresets. In: 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics; 2024:220-233. doi:10.1137/1.9781611977929.17
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18116 |
La Tour MD, Henzinger M, Saulpic D. Making old things new: A unified algorithm for differentially private clustering. In: Proceedings of the 41st International Conference on Machine Learning. Vol 235. ML Research Press; 2024:12046-12086.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18928 |
Henzinger M, Saha B, Seybold MP, Ye C. On the complexity of algorithms with predictions for dynamic graph problems. In: 15th Innovations in Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024:62:1-62:25. doi:10.4230/LIPIcs.ITCS.2024.62
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15093 |
Cultrera di Montesano S, Edelsbrunner H, Henzinger M, Ost L. Dynamically maintaining the persistent homology of time series. In: Woodruff DP, ed. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics; 2024:243-295. doi:10.1137/1.9781611977912.11
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 19512 |
Andersson JD, Henzinger M, Pagh R, Steiner TA, Upadhyay J. Continual counting with gradual privacy expiration. In: 38th Conference on Neural Information Processing Systems. Vol 37. Neural Information Processing Systems Foundation; 2024.
[Preprint]
View
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18503 |
Henzinger M, Li J, Rao S, Wang D. Deterministic near-linear time minimum cut in weighted graphs. In: 35th Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2024:3089-3139. doi:10.1137/1.9781611977912.111
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15008 |
Goranci G, Henzinger M, Räcke H, Sachdeva S, Sricharan AR. Electrical flows for polylogarithmic competitive oblivious routing. In: 15th Innovations in Theoretical Computer Science Conference. Vol 287. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2024. doi:10.4230/LIPIcs.ITCS.2024.55
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18906 |
Hanauer K, Henzinger M, Münk R, Räcke H, Vötsch M. Expander hierarchies for normalized cuts on graphs. In: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. ACM; 2024:1016-1027. doi:10.1145/3637528.3671978
[Published Version]
View
| Files available
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18922
Georgiadis L, Italiano GF, Kosinas E. Computing the 3-edge-connected components of directed graphs in linear time. In: 65th Annual Symposium on Foundations of Computer Science. IEEE; 2024:62-85. doi:10.1109/focs61266.2024.00015
View
| DOI