6 papers · 1 filter
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 -approximate - maximum flow in undirected, uncapacitated -vertex graphs undergoing edge insertion…
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…
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…
Differentially Private Continual Release of Histograms and Related Queries
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
We study privately releasing column sums of a -dimensional table with entries from a universe undergoing row updates, called histogram under continual release. Our mech…
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…
Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
Monika Henzinger, A. R. Sricharan, Leqi Zhu
Computing the core decomposition of a graph is a fundamental problem that has recently been studied in the differentially private setting, motivated by practical applications in da…