Henzinger_Monika Group
Algorithms
To save resources in computing the goal is usually to minimize computing time and storage space. The research field of efficient algorithms and data structures wants to understand how to save these resources, both by designing better algorithms and by proving bounds on the limits of possible savings. One particular area of focus in our research on efficient algorithms are dynamic settings where the input to the program is updated repeatedly and after each update the new solution needs to be found much faster than restarting the computation on the new input.
A second area of our research is designing algorithms that protect the privacy of the input data. This can be achieved by adding suitable noise to the input and the goal of the research is to minimize the amount of noise as it reduces the information that can be gained from the output and can also slow down the algorithm. The amount of noise depends on what information needs to be computed from the data and what kind of privacy guarantees are desired. Again, our focus is on the dynamic setting where the input data changes continuously.
A third area of our research is to turn the theoretically best algorithms into simple, practical algorithms that we implement and evaluate empirically. As before we are especially interested in algorithms for dynamically changing inputs.
Group Leader
Administrative Support
Team
Current Projects
- ERC Advanced Grant “The design and evaluation of modern fully dynamic data structures”
- Wittgenstein Award of the Austrian Science Fund
- WEAVE project “Static and dynamic hierarchical graph decompositions” of the Austrian Science Fund
- Principal Investigator project “Fast algorithms for a reactive network layer” of the Austrian Science Fund
Recent Publications
El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes and adversarial edges. 38th International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 319, 21. View
La Tour MD, Henzinger M, Saulpic D. 2024. Fully dynamic k-means coreset in near-optimal update time. 32nd Annual European Symposium on Algorithms. ESA: European Symposium on Algorithms, LIPIcs, vol. 308, 100. View
Henzinger M, Sricharan AR, Steiner TA. 2024. Private counting of distinct elements in the turnstile model and extensions. International Conference on Approximation Algorithms for Combinatorial Optimization Problems . APPROX: Conference on Approximation Algorithms for Combinatorial Optimization Problems, LIPIcs, vol. 317, 40. View
Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M. 2024. Data-efficient learning via clustering-based sensitivity sampling: Foundation models and beyond. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 2086–2107. View
La Tour MD, Henzinger M, Saulpic D. 2024. Making old things new: A unified algorithm for differentially private clustering. Proceedings of the 41st International Conference on Machine Learning. ICML: International Conference on Machine Learning, PMLR, vol. 235, 12046–12086. View
ReX-Link: Monika Henzinger
Career
since 2023 Professor, Institute of Science and Technology Austria (ISTA)
2009 – 2023 Professor, University of Vienna
2005 – 2009 Professor, EPFL, Switzerland
1999 – 2005 Google
1996 – 1999 Digital Equipment Corporation
1993 – 1996 Assistant Professor at Cornell University, USA
1993 PhD Princeton University, USA
Selected Distinctions
2021 Wittgenstein Award
2021 ERC Advanced Grant
2019 Stanford University Distinguished Visiting Austrian Chair
2019 Carus medal of the German Academy of Sciences Leopoldina
2018 Science Award of the City of Vienna
2017 SIGIR Test of Time Award
2017 Member of the Austrian Academy of Sciences
2016 Fellow of the Association of Computing Machinery
2014 Member of the German Academy of Sciences Leopoldina
2014 Fellow of the European Association of Theoretical Computer Science
2014 ERC Advanced Grant
2013 Honorary Doctorate of the Technical University of Dortmund, Germany
2013 Member of the Academia Europaea
2004 European Young Investigator Award of the European Science Foundation
2001 Top 25 Women on the Web Award
1995: CAREER Development Award of the National Science Foundation
