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.
27 Publications
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.
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
| arXiv
B. Hu, E. Kosinas, A. Polak, in:, 32nd Annual European Symposium on Algorithms, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
2024 | Published | Journal Article | IST-REx-ID: 17188 |
Delegated online search
P. Braun, N. Hahn, M. Hoefer, C. Schecker, Artificial Intelligence 334 (2024).
[Published Version]
View
| Files available
| DOI
| arXiv
P. Braun, N. Hahn, M. Hoefer, C. Schecker, Artificial Intelligence 334 (2024).
2024 | Published | Conference Paper | IST-REx-ID: 18922
Computing the 3-edge-connected components of directed graphs in linear time
Georgiadis, Loukas, Computing the 3-edge-connected components of directed graphs in linear time. 65th Annual Symposium on Foundations of Computer Science. 2024
View
| DOI
Georgiadis, Loukas, Computing the 3-edge-connected components of directed graphs in linear time. 65th Annual Symposium on Foundations of Computer Science. 2024
2024 | Published | Conference Paper | IST-REx-ID: 18557 |
Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges
A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
[Published Version]
View
| Files available
| DOI
| arXiv
A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
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
| 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: 15008 |
Electrical flows for polylogarithmic competitive oblivious routing
Goranci, Gramoz, Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference 287. 2024
[Published Version]
View
| Files available
| DOI
| arXiv
Goranci, Gramoz, Electrical flows for polylogarithmic competitive oblivious routing. 15th Innovations in Theoretical Computer Science Conference 287. 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
| 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: 18906 |
Expander hierarchies for normalized cuts on graphs
Hanauer, Kathrin, Expander hierarchies for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024
[Published Version]
View
| Files available
| DOI
Hanauer, Kathrin, Expander hierarchies for normalized cuts on graphs. Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2024
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: 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
| 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.
2024 | Published | Conference Paper | IST-REx-ID: 15253 |
A unifying framework for differentially private sums under continual observation
M. Henzinger, J. Upadhyay, S. Upadhyay, in:, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
M. Henzinger, J. Upadhyay, S. Upadhyay, in:, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018.
2024 | Published | Conference Paper | IST-REx-ID: 14769 |
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
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.
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: 18928 |
On the complexity of algorithms with predictions for dynamic graph problems
M. Henzinger, B. Saha, M.P. Seybold, C. Ye, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25.
[Published Version]
View
| Files available
| DOI
| arXiv
M. Henzinger, B. Saha, M.P. Seybold, C. Ye, in:, 15th Innovations in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 62:1-62:25.
2024 | Published | Conference Paper | IST-REx-ID: 15093 |
Dynamically maintaining the persistent homology of time series
S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, L. Ost, in:, D.P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, 2024, pp. 243–295.
2024 | Published | Conference Paper | IST-REx-ID: 19512 |
Continual counting with gradual privacy expiration
J.D. Andersson, M. Henzinger, R. Pagh, T.A. Steiner, J. Upadhyay, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024.
[Preprint]
View
| Download Preprint (ext.)
| arXiv
J.D. Andersson, M. Henzinger, R. Pagh, T.A. Steiner, J. Upadhyay, in:, 38th Conference on Neural Information Processing Systems, Neural Information Processing Systems Foundation, 2024.
2023 | Published | Conference Paper | IST-REx-ID: 14086 |
Faster submodular maximization for several classes of matroids
Henzinger, Monika H, Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming 261. 2023
[Published Version]
View
| Files available
| DOI
| arXiv
Henzinger, Monika H, Faster submodular maximization for several classes of matroids. 50th International Colloquium on Automata, Languages, and Programming 261. 2023
2023 | Published | Conference Paper | IST-REx-ID: 14768 |
Deterministic clustering in high dimensional spaces: Sketches and approximation
Cohen-Addad, Vincent, Deterministic clustering in high dimensional spaces: Sketches and approximation. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science. 2023
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
Cohen-Addad, Vincent, Deterministic clustering in high dimensional spaces: Sketches and approximation. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science. 2023