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.” Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 5, Association for Computing Machinery, 2025, pp. 2951–70, doi:10.1137/1.9781611978322.95.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Journal Article | IST-REx-ID: 17188 |
Braun, Pirmin, et al. “Delegated Online Search.” Artificial Intelligence, vol. 334, 104171, Elsevier, 2024, doi:10.1016/j.artint.2024.104171.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18906 |
Hanauer, Kathrin, et al. “Expander Hierarchies for Normalized Cuts on Graphs.” Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, ACM, 2024, pp. 1016–27, doi:10.1145/3637528.3671978.
[Published Version]
View
| Files available
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18922
Georgiadis, Loukas, et al. “Computing the 3-Edge-Connected Components of Directed Graphs in Linear Time.” 65th Annual Symposium on Foundations of Computer Science, IEEE, 2024, pp. 62–85, doi:10.1109/focs61266.2024.00015.
View
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18928 |
Henzinger, Monika, et al. “On the Complexity of Algorithms with Predictions for Dynamic Graph Problems.” 15th Innovations in Theoretical Computer Science Conference, vol. 287, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, p. 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: 14769 |
Henzinger, Monika, et al. “Experimental Evaluation of Fully Dynamic K-Means via Coresets.” 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Society for Industrial and Applied Mathematics, 2024, pp. 220–33, doi:10.1137/1.9781611977929.17.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15093 |
Cultrera di Montesano, Sebastiano, et al. “Dynamically Maintaining the Persistent Homology of Time Series.” Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), edited by David P. Woodruff, Society for Industrial and Applied Mathematics, 2024, pp. 243–95, doi:10.1137/1.9781611977912.11.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15008 |
Goranci, Gramoz, et al. “Electrical Flows for Polylogarithmic Competitive Oblivious Routing.” 15th Innovations in Theoretical Computer Science Conference, vol. 287, 55, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi: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, doi: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, et al. “A Unifying Framework for Differentially Private Sums under Continual Observation.” Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, vol. 2024, Society for Industrial and Applied Mathematics, 2024, pp. 995–1018, doi:10.1137/1.9781611977912.38.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18115 |
Axiotis, Kyriakos, et al. “Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond.” Proceedings of the 41st International Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 2086–107.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18116 |
La Tour, Max Dupré, et al. “Making Old Things New: A Unified Algorithm for Differentially Private Clustering.” Proceedings of the 41st International Conference on Machine Learning, vol. 235, ML Research Press, 2024, pp. 12046–86.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18156 |
Henzinger, Monika, et al. “Private Counting of Distinct Elements in the Turnstile Model and Extensions.” International Conference on Approximation Algorithms for Combinatorial Optimization Problems , vol. 317, 40, 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, Max Dupré, et al. “Fully Dynamic K-Means Coreset in near-Optimal Update Time.” 32nd Annual European Symposium on Algorithms, vol. 308, 100, 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: 18309 |
Hu, Bingbing, et al. “Connectivity Oracles for Predictable Vertex Failures.” 32nd Annual European Symposium on Algorithms, vol. 308, 72, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi:10.4230/LIPIcs.ESA.2024.72.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18503
Henzinger, Monika, et al. “Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.” 35th Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2024, pp. 3089–139, doi:10.1137/1.9781611977912.111.
[Preprint]
View
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18557 |
El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial Edges.” 38th International Symposium on Distributed Computing, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024, doi: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.” International Conference on Integer Programming and Combinatorial Optimization, vol. 13904, Springer Nature, 2023, pp. 453–65, doi: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, et al. “A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems.” Algorithmica, vol. 85, Springer Nature, 2023, pp. 2680–3716, doi: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.” 50th International Colloquium on Automata, Languages, and Programming, vol. 261, 69, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPIcs.ICALP.2023.69.
[Published Version]
View
| Files available
| DOI