Monika Henzinger

Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity

Antoine El-Hayek, Monika Henzinger, Da Wei Zheng

Having simple algorithms is important for the practical adoption of new algorithms. However, simplifying existing algorithms is a field that does not usually receive a lot of atten…

Edit-Neighboring Data Streams and Privacy under Continual Observation

Joel Daniel Andersson, Anamay Chaturvedi, Monika Henzinger +1

Differential privacy under Continual Observation (CO) quantifies the loss in privacy that occurs when outputs generated using a stream of sensitive input data are published in the…

Near-Optimal Generalized Private Testing

Anamay Chaturvedi, Monika Henzinger, Jalaj Upadhyay

In differential privacy (DP), the generalized private testing problem was introduced by Liu and Talwar (STOC 2019). Given a dataset $X \in X$ and a sequence of black-box…

Dynamic Hierarchical $j$ -Tree Decomposition and Its Applications

Gramoz Goranci, Monika Henzinger, Peter Kiss +2

We develop a new algorithmic framework for designing approximation algorithms for cut-based optimization problems on capacitated undirected graphs that undergo edge insertions and…

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time

Monika Henzinger, Robin Münk, Harald Räcke

A single-commodity congestion approximator for a graph is a compact data structure that approximately predicts the edge congestion required to route any set of single-commodity flo…

Improved Lower Bounds for Privacy under Continual Release

Bardiya Aryanfard, Monika Henzinger, David Saulpic +1

We study the problem of continually releasing statistics of an evolving dataset under differential privacy. In the event-level setting, we show the first polynomial lower bounds on…

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time

Antoine El-Hayek, Monika Henzinger, Jason Li

We present an exact fully-dynamic minimum cut algorithm that runs in $n^{o (1)}$ deterministic update time when the minimum cut size is at most $2^{Θ (l o g^{3/4 - c} n)}$ for any $c > 0$ ,…

Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting

Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay

The factorization norms of the lower-triangular all-ones $n \times n$ matrix, $γ_{2} (M_{co u n t})$ and $γ_{F} (M_{co u n t})$ , play a central role in differential privacy as they are used…

Efficient Contractions of Dynamic Graphs -- with Applications

Monika Henzinger, Evangelos Kosinas, Robin Münk +1

A non-trivial minimum cut (NMC) sparsifier is a multigraph $G^$ that preserves all non-trivial minimum cuts of a given undirected graph $G$ . We introduce a flexible data struc…

Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism

Laxman Dhulipala, Monika Henzinger, George Z. Li +3

Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k…

cs.LG2025★ 2 cited

Correlated Noise Mechanisms for Differentially Private Learning

Krishna Pillutla, Jalaj Upadhyay, Christopher A. Choquette-Choo +9

This monograph explores the design and analysis of correlated noise mechanisms for differential privacy (DP), focusing on their application to private training of AI and machine le…

cs.DS2025★ 1 cited

Binned Group Algebra Factorization for Differentially Private Continual Counting

Monika Henzinger, Nikita P. Kalinin, Jalaj Upadhyay

We study memory-efficient matrix factorization for differentially private counting under continual observation. While recent work by Henzinger and Upadhyay 2024 introduced a factor…

Incremental Approximate Maximum Flow via Residual Graph Sparsification

Gramoz Goranci, Monika Henzinger, Harald Räcke +1

We give an algorithm that, with high probability, maintains a $(1 - ε)$ -approximate $s$ - $t$ maximum flow in undirected, uncapacitated $n$ -vertex graphs undergoing $m$ edge insertions…

Improved Differentially Private Continual Observation Using Group Algebra

Monika Henzinger, Jalaj Upadhyay

Differentially private weighted prefix sum under continual observation is a crucial component in the production-level deployment of private next-word prediction for Gboard, which,…

Concurrent Composition for Differentially Private Continual Mechanisms

Monika Henzinger, Roodabeh Safavi, Salil Vadhan

Many intended uses of differential privacy involve a $continual mechanism$ that is set up to run continuously over a long period of time, making more statistical releases…

Private Counting of Distinct Elements in the Turnstile Model and Extensions

Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner

Privately counting distinct elements in a stream is a fundamental data analysis problem with many applications in machine learning. In the turnstile model, Jain et al. [NeurIPS2023…

Fully Dynamic k-Means Coreset in Near-Optimal Update Time

Max Dupré la Tour, Monika Henzinger, David Saulpic

We study in this paper the problem of maintaining a solution to $k$ -median and $k$ -means clustering in a fully dynamic setting. To do so, we present an algorithm to efficiently mai…