Skip to main content

Discrete Algorithms and Differential Privacy

Computer Science

Image of Monika Henzinger

Monika Henzinger

Professor


1 Career

  • Since 2024 Vice President for Technology Transfer, Institute of Science and Technology Austria (ISTA)
  • Since 2023 Professor, Institute of Science and Technology Austria (ISTA)
  • 2009 – 2023 Professor, University of Vienna
  • 2021 Visiting Professor, Stanford University, USA
  • 2015 Visiting Scientist, Simons Institute for the Theory of Computing at UC Berkeley, USA
  • 2005 – 2009 Professor of Computer Science, École Polytechnique Fédérale de Lausanne, Switzerland
  • 1999 – 2005 Director of Research, Google Inc., Mountain View, CA, USA
  • 1996 – 1999 Research Staff, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, USA
  • 1993 – 1996 Assistant Professor of Computer Science, Cornell University, Ithaca, CA, USA

1.1 Selected Distinctions

  • 2025 Invited keynote ACM Symposium on the Theory of Computing (STOC)
  • 2024 Best Paper Award ACM-SIAM Symposium on Discrete Algorithms
  • 2021 Wittgenstein Award of the Austrian Science Fund
  • 2019 Carus Medal of the German Academy of Sciences (Leopoldina)
  • 2016 Fellow of the Association of Computing Machiner

1.2 Selected Grants

  • 2023 – 2026 FWF International Collaboration (with Harald Räcke, TU Munich): Static and Dynamic Hierarchical Graph Decompositions, PI € 145,000.
  • 2022 – 2028 ERC Advanced Grant, The Design of Modern Fully Dynamic Data Structures, PI € 2,477,000.
  • 2022 – 2029 FWF Wittgenstein Award, PI, € 1,500,000.

1.3 Tech Transfer (Patents, Spin-Offs)

N/A


1.4 Selected Publications

  1. A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time,” in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026, K. G. Larsen and B. Saha, Eds., SIAM, 2026, pp. 613–663. DOI: 10.1137/1.9781611978971.25. [Online]. Available: https://doi.org/10.1137/1.9781611978971.25.
  2. 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, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, Y. Azar and D. Panigrahi, Eds., SIAM, 2025, pp. 2951–2970. DOI: 10.1137/1.9781611978322.95. [Online]. Available: https://doi.org/10.1137/1.9781611978322.95.
  3. M. Henzinger, J. Li, S. Rao, and D. Wang, “Deterministic near-linear time minimum cut in weighted graphs,” in Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, D. P. Woodruff, Ed., SIAM, 2024, pp. 3089–3139. DOI: 10.1137/1.9781611977912.111. [Online]. Available: https://doi.org/10.1137/1.9781611977912.111.
  4. H. Fichtenberger, M. Henzinger, and J. Upadhyay, “Constant matters: Fine-grained error bound on differentially private continual observation,” in International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, Eds., ser. Proceedings of Machine Learning Research, PMLR, 2023, pp. 10 072–10 092. [Online]. Available: https://proceedings.mlr.press/v202/fichtenberger23a.html.
  5. M. Henzinger, S. Krinninger, and D. Nanongkai, “Decremental single-source shortest paths on undirected graphs in near-linear total update time,” J. ACM, vol. 65, no. 6, 36:1–36:40, 2018. DOI: 10.1145/3218657. [Online]. Available: https://doi.org/10.1145/3218657.

2 Group Members

  • Bardiya Aryanfard, PhD Student since 2024
  • Antoine El-Hayek, PhD Student since 2022
  • Roodabeh Safavi, PhD Student since 2023
  • Joel Andersson, Postdoc since 2025
  • Anamay Chaturvedi, Postdoc since 2024
  • Daniel Rutschmann, Postdoc since 202
  • Da Wei Zheng, Postdoc since 2025

3 Research

Algorithms are the backbone of every computer program. Thus the design of algorithms with desired properties is crucial for our technological advancement. The research field on algorithms consists of (a) the design of algorithms, and (b) proving that algorithms with certain properties cannot exist. My research works on both aspects. Topic-wise it focuses on (1) (computation) time and (memory) space efficient graph algorithms, which are saving resources and on large datasets are crucial for enabling the computation of a solution at all, and (2) privacy-protecting algorithms which allow to perform data analysis while protecting the privacy of the underlying data.


3.1 Current Scientific Projects/Directions

  • Efficient graph algorithms, specifically dynamic graph algorithms, which are algorithms that maintain desired graph properties while the graph is being modified. The goal is to compute the property on a slightly modified graph very efficiently if the solution for the original graph has already been computed.
  • Differentially private algorithms, specifically in the setting where the input changes dynamically and where for each modified dataset an answer to a data analysis problem has to be given. The challenge is that giving many answers might disclose much more information about the underlying dataset than giving just one answer. Thus, we are studying how much random noise has to be used for these answers to guarantee privacy for the underlying private dataset, while still providing useful answers.
The crucial graph decomposition needed in our new mininum cut algorithm.
Figure 1: Picture illustrating the crucial graph decomposition needed in our new mininum cut algorithm.

3.2 Research in Focus

A graph is a network consisting of nodes and edges, where each edge connects two nodes. To be more expressive, edges are frequently assigned a weight. Finding “bottlenecks” in graphs is important, for example, in communication or transportation networks, as it shows potential “problematic points”. One such bottleneck of interest in the mininum cut, which is the minimum (by weight or number) set of edges whose removal disconnects the graph. For example, the minimum cut gives the minimum set of shipping channels that need to be blocked so that it is no longer possible to ship from every place in the world to every other place. On huge graphs it is important to be able to compute minimum cuts very efficiently, where efficiency is measured in the size of the graph. In the 1990s Karger and Stein gave a near-linear time (ie a very fast) randomized algorithm for computing a minimum cut in a weighted graph. Randomized algorithms, however, assume that a computer has access to random bits (which is unrealistic) and have the disadvantage that with a certain (small) probability they might give a wrong answer. In 2024 we published the first deterministic near-linear time algorithm for computing a minimum cut in a weighted graph. A deterministic algorithm does not need access to random bits and always gives the correct answer. This paper received the best paper award at the ACM-SIAM Symposium on Discrete Algorithms (SODA) 2024, which is one of the top three conferences in theoretical computer science.
Citation: Monika Henzinger, Jason Li, Satish Rao, Di Wang: Deterministic Near-Linear Time Minimum Cut in Weighted Graphs. SODA 2024: 3089-3139



theme sidebar-arrow-up
Back to Top