1 citations · 1 across the 3 of their papers we have counts for
9 papers · 1 filter
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…
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 insertions…
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…
Differentially Private Histogram, Predecessor, and Set Cardinality under Continual Observation
Monika Henzinger, A. R. Sricharan, Teresa Anna Steiner
Differential privacy is the de-facto privacy standard in data analysis. The classic model of differential privacy considers the data to be static. The dynamic setting, called diffe…
Electrical Flows for Polylogarithmic Competitive Oblivious Routing
Gramoz Goranci, Monika Henzinger, Harald Räcke +2
Oblivious routing is a well-studied paradigm that uses static precomputed routing tables for selecting routing paths within a network. Existing oblivious routing schemes with polyl…
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 mecha…
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
Monika Henzinger, Ami Paz, A. R. Sricharan
A dynamic graph algorithm is a data structure that answers queries about a property of the current graph while supporting graph modifications such as edge insertions and deletions.…