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.
35 Publications
2025 | Published | Conference Paper | IST-REx-ID: 19038 | 
M. Henzinger and J. Upadhyay, “Improved differentially private continual observation using group algebra,” in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2025, vol. 5, pp. 2951–2970.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20301 |
M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Differentially private continual release of histograms and related queries,” in The 28th International Conference on Artificial Intelligence and Statistics, Mai Khao, Thailand, 2025, vol. 258, pp. 1990–1998.
[Preprint]
View
| Download Preprint (ext.)
| arXiv
2025 | Published | Journal Article | IST-REx-ID: 15121 |
D. W. Zheng and M. Henzinger, “Multiplicative auction algorithm for approximate maximum weight bipartite matching,” Mathematical Programming, vol. 210. Springer Nature, pp. 881–894, 2025.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| WoS
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 19858 |
A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic maximum k-edge coloring,” in 4th Symposium on Algorithmic Foundations of Dynamic Networks, Liverpool, United Kingdom, 2025, vol. 330.
[Published Version]
View
| Files available
| DOI
| WoS
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20052 |
T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Brief announcement: Minimizing energy solves relative majority with a cubic number of states in population protocols,” in Proceedings of the ACM Symposium on Principles of Distributed Computing, Huatulco, Mexico, 2025, pp. 549–552.
[Published Version]
View
| Files available
| DOI
| WoS
2025 | Published | Conference Paper | IST-REx-ID: 20051 |
A. El-Hayek, R. Elsässer, and S. Schmid, “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, Huatulco, Mexico, 2025.
[Published Version]
View
| Files available
| DOI
| WoS
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20535 |
L. Dhulipala, M. Henzinger, G. Z. Li, Q. C. Liu, A. R. Sricharan, and L. Zhu, “Near-optimal differentially private graph algorithms via the Multidimensional AboveThreshold Mechanism,” in 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351.
[Published Version]
View
| Files available
| DOI
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20536 |
R. Safavi Hemami and M. P. Seybold, “B-Treaps revised: Write efficient randomized block search trees with high load,” in 19th International Symposium on Algorithms and Data Structures, Toronto, Canada, 2025, vol. 349.
[Published Version]
View
| Files available
| DOI
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20534 |
M. Henzinger, E. Kosinas, R. Münk, and H. Räcke, “Efficient contractions of dynamic graphs - with applications,” in 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351.
[Published Version]
View
| Files available
| DOI
| arXiv
2025 | Published | Conference Paper | IST-REx-ID: 20533 |
M. Henzinger and R. Safavi Hemami, “Securing dynamic data: A primer on differentially private data structures,” in 33rd Annual European Symposium on Algorithms, Warsaw, Poland, 2025, vol. 351.
[Published Version]
View
| Files available
| DOI
2024 | Published | Conference Paper | IST-REx-ID: 18309 |
B. Hu, E. Kosinas, and A. Polak, “Connectivity oracles for predictable vertex failures,” in 32nd Annual European Symposium on Algorithms, London, United Kingdom, 2024, vol. 308.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18557 |
A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges,” in 38th International Symposium on Distributed Computing, Madrid, Spain, 2024, vol. 319.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18156 |
M. Henzinger, A. R. Sricharan, and T. A. Steiner, “Private counting of distinct elements in the turnstile model and extensions,” in International Conference on Approximation Algorithms for Combinatorial Optimization Problems , London, United Kingdom, 2024, vol. 317.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18308 |
M. D. La Tour, M. Henzinger, and D. Saulpic, “Fully dynamic k-means coreset in near-optimal update time,” in 32nd Annual European Symposium on Algorithms, London, United Kingdom, 2024, vol. 308.
[Published Version]
View
| Files available
| DOI
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18115 |
K. Axiotis et al., “Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond,” in Proceedings of the 41st International Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 2086–2107.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15253 |
M. Henzinger, J. Upadhyay, and S. Upadhyay, “A unifying framework for differentially private sums under continual observation,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms, Alexandria, VA, United States, 2024, vol. 2024, pp. 995–1018.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 14769 |
M. Henzinger, D. Saulpic, and L. Sidl, “Experimental evaluation of fully dynamic k-means via coresets,” in 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments, Alexandria, VA, United States, 2024, pp. 220–233.
[Preprint]
View
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 18116 |
M. D. La Tour, M. Henzinger, and D. Saulpic, “Making old things new: A unified algorithm for differentially private clustering,” in Proceedings of the 41st International Conference on Machine Learning, Vienna, Austria, 2024, vol. 235, pp. 12046–12086.
[Published Version]
View
| Download Published Version (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 15093 |
S. Cultrera di Montesano, H. Edelsbrunner, M. Henzinger, and L. Ost, “Dynamically maintaining the persistent homology of time series,” in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Alexandria, VA, USA, 2024, pp. 243–295.
[Preprint]
View
| Files available
| DOI
| Download Preprint (ext.)
| arXiv
2024 | Published | Conference Paper | IST-REx-ID: 19512 |
J. D. Andersson, M. Henzinger, R. Pagh, T. A. Steiner, and J. Upadhyay, “Continual counting with gradual privacy expiration,” in 38th Conference on Neural Information Processing Systems, Vancouver, Canada, 2024, vol. 37.
[Preprint]
View
| Download Preprint (ext.)
| arXiv