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, M., & Upadhyay, J. (2025). Improved differentially private continual observation using group algebra. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 5, pp. 2951–2970). New Orleans, LA, United States: Association for Computing Machinery. https://doi.org/10.1137/1.9781611978322.95
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Journal Article | IST-REx-ID: 17188 |
Braun, P., Hahn, N., Hoefer, M., & Schecker, C. (2024). Delegated online search. Artificial Intelligence. Elsevier. 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, K., Henzinger, M., Münk, R., Räcke, H., & Vötsch, M. (2024). Expander hierarchies for normalized cuts on graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (pp. 1016–1027). Barcelona, Spain: ACM. https://doi.org/10.1145/3637528.3671978
[Published Version]
View
| Files available
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18922
Georgiadis, L., Italiano, G. F., & Kosinas, E. (2024). Computing the 3-edge-connected components of directed graphs in linear time. In 65th Annual Symposium on Foundations of Computer Science (pp. 62–85). Chicago, IL, United States: IEEE. https://doi.org/10.1109/focs61266.2024.00015
View
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18928 |
Henzinger, M., Saha, B., Seybold, M. P., & Ye, C. (2024). On the complexity of algorithms with predictions for dynamic graph problems. In 15th Innovations in Theoretical Computer Science Conference (Vol. 287, p. 62:1-62:25). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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, M., Saulpic, D., & Sidl, L. (2024). Experimental evaluation of fully dynamic k-means via coresets. In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (pp. 220–233). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. 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, S., Edelsbrunner, H., Henzinger, M., & Ost, L. (2024). Dynamically maintaining the persistent homology of time series. In D. P. Woodruff (Ed.), Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 243–295). Alexandria, VA, USA: Society for Industrial and Applied Mathematics. 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, G., Henzinger, M., Räcke, H., Sachdeva, S., & Sricharan, A. R. (2024). Electrical flows for polylogarithmic competitive oblivious routing. In 15th Innovations in Theoretical Computer Science Conference (Vol. 287). Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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, D. W., & Henzinger, M. (2024). Multiplicative auction algorithm for approximate maximum weight bipartite matching. Mathematical Programming. Springer Nature. 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, M., Upadhyay, J., & Upadhyay, S. (2024). A unifying framework for differentially private sums under continual observation. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (Vol. 2024, pp. 995–1018). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.38
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18115 |
Axiotis, K., Cohen-Addad, V., Henzinger, M., Jerome, S., Mirrokni, V., Saulpic, D., … Wunder, M. (2024). Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. In Proceedings of the 41st International Conference on Machine Learning (Vol. 235, pp. 2086–2107). Vienna, Austria: ML Research Press.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18116 |
La Tour, M. D., Henzinger, M., & Saulpic, D. (2024). Making old things new: A unified algorithm for differentially private clustering. In Proceedings of the 41st International Conference on Machine Learning (Vol. 235, pp. 12046–12086). Vienna, Austria: ML Research Press.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18156 |
Henzinger, M., Sricharan, A. R., & Steiner, T. A. (2024). Private counting of distinct elements in the turnstile model and extensions. In International Conference on Approximation Algorithms for Combinatorial Optimization Problems (Vol. 317). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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, M. D., Henzinger, M., & Saulpic, D. (2024). Fully dynamic k-means coreset in near-optimal update time. In 32nd Annual European Symposium on Algorithms (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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, B., Kosinas, E., & Polak, A. (2024). Connectivity oracles for predictable vertex failures. In 32nd Annual European Symposium on Algorithms (Vol. 308). London, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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, M., Li, J., Rao, S., & Wang, D. (2024). Deterministic near-linear time minimum cut in weighted graphs. In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 3089–3139). Alexandria, VA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611977912.111
[Preprint]
View
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18557 |
El-Hayek, A., Henzinger, M., & Schmid, S. (2024). Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. In 38th International Symposium on Distributed Computing (Vol. 319). Madrid, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 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, D. W., & Henzinger, M. (2023). Multiplicative auction algorithm for approximate maximum weight bipartite matching. In International Conference on Integer Programming and Combinatorial Optimization (Vol. 13904, pp. 453–465). Madison, WI, United States: Springer Nature. 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, M., Jin, B., Peng, R., & Williamson, D. P. (2023). A combinatorial cut-toggling algorithm for solving Laplacian linear systems. Algorithmica. Springer Nature. 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, G., & Henzinger, M. (2023). Efficient data structures for incremental exact and approximate maximum flow. In 50th International Colloquium on Automata, Languages, and Programming (Vol. 261). Paderborn, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ICALP.2023.69
[Published Version]
View
| Files available
| DOI