2 citations · 3 across the 6 of their papers we have counts for
12 papers
Dynamic Hierarchical -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 deterministic update time when the minimum cut size is at most for any ,…
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 matrix, and , play a central role in differential privacy as they are used…
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…