Please note that ISTA Research Explorer no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
26 Publications
2025 | Published | Conference Paper | IST-REx-ID: 19038 | 
Henzinger, Monika, and Jalaj Upadhyay. “Improved Differentially Private Continual Observation Using Group Algebra.” In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 5:2951–70. Association for Computing Machinery, 2025. https://doi.org/10.1137/1.9781611978322.95.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Journal Article | IST-REx-ID: 17188 |
Braun, Pirmin, Niklas Hahn, Martin Hoefer, and Conrad Schecker. “Delegated Online Search.” Artificial Intelligence. Elsevier, 2024. https://doi.org/10.1016/j.artint.2024.104171.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18906 |
Hanauer, Kathrin, Monika Henzinger, Robin Münk, Harald Räcke, and Maximilian Vötsch. “Expander Hierarchies for Normalized Cuts on Graphs.” In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 1016–27. ACM, 2024. https://doi.org/10.1145/3637528.3671978.
[Published Version]
View
| Files available
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18922
Georgiadis, Loukas, Giuseppe F. Italiano, and Evangelos Kosinas. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” In 65th Annual Symposium on Foundations of Computer Science, 62–85. IEEE, 2024. https://doi.org/10.1109/focs61266.2024.00015.
View
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18928 |
Henzinger, Monika, Barna Saha, Martin P. Seybold, and Christopher Ye. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” In 15th Innovations in Theoretical Computer Science Conference, 287:62:1-62:25. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ITCS.2024.62.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 14769 |
Henzinger, Monika, David Saulpic, and Leonhard Sidl. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, 220–33. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977929.17.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15093 |
Cultrera di Montesano, Sebastiano, Herbert Edelsbrunner, Monika Henzinger, and Lara Ost. “Dynamically Maintaining the Persistent Homology of Time Series.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, 243–95. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.11.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15008 |
Goranci, Gramoz, Monika Henzinger, Harald Räcke, Sushant Sachdeva, and A. R. Sricharan. “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. https://doi.org/10.4230/LIPIcs.ITCS.2024.55.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Epub ahead of print | Journal Article | IST-REx-ID: 15121 |
Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” Mathematical Programming. Springer Nature, 2024. https://doi.org/10.1007/s10107-024-02066-3.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15253 |
Henzinger, Monika, Jalaj Upadhyay, and Sarvagya Upadhyay. “A Unifying Framework for Differentially Private Sums under Continual Observation.” In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, 2024:995–1018. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.38.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18115 |
Axiotis, Kyriakos, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, and Michael Wunder. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” In Proceedings of the 41st International Conference on Machine Learning, 235:2086–2107. ML Research Press, 2024.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18116 |
La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” In Proceedings of the 41st International Conference on Machine Learning, 235:12046–86. ML Research Press, 2024.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18156 |
Henzinger, Monika, A. R. Sricharan, and Teresa Anna Steiner. “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. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2024.40.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18308 |
La Tour, Max Dupré, Monika Henzinger, and David Saulpic. “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. https://doi.org/10.4230/LIPIcs.ESA.2024.100.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18309 |
Hu, Bingbing, Evangelos Kosinas, and Adam Polak. “Connectivity Oracles for Predictable Vertex Failures.” In 32nd Annual European Symposium on Algorithms, Vol. 308. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.ESA.2024.72.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18503
Henzinger, Monika, Jason Li, Satish Rao, and Di Wang. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” In 35th Annual ACM-SIAM Symposium on Discrete Algorithms, 3089–3139. Society for Industrial and Applied Mathematics, 2024. https://doi.org/10.1137/1.9781611977912.111.
[Preprint]
View
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18557 |
El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “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. https://doi.org/10.4230/LIPIcs.DISC.2024.21.
[Published Version]
View
| Files available
| DOI
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 13236 |
Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching.” In International Conference on Integer Programming and Combinatorial Optimization, 13904:453–65. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32726-1_32.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2023 | Published | Journal Article | IST-REx-ID: 14043 |
Henzinger, Monika, Billy Jin, Richard Peng, and David P. Williamson. “A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.” Algorithmica. Springer Nature, 2023. https://doi.org/10.1007/s00453-023-01154-8.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2023 | Published | Conference Paper | IST-REx-ID: 14085 |
Goranci, Gramoz, and Monika Henzinger. “Efficient Data Structures for Incremental Exact and Approximate Maximum Flow.” In 50th International Colloquium on Automata, Languages, and Programming, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. https://doi.org/10.4230/LIPIcs.ICALP.2023.69.
[Published Version]
View
| Files available
| DOI