19 citations · 63 across the 17 of their papers we have counts for
10 papers · 1 filter
Differentially Private Heatmaps
Badih Ghazi, Junfeng He, Kai Kohlhoff +4
We consider the task of producing heatmaps from users' aggregated data while protecting their privacy. We give a differentially private (DP) algorithm for this task and demonstrate…
Private Counting of Distinct and k-Occurring Items in Time Windows
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
In this work, we study the task of estimating the numbers of distinct and -occurring items in a time window under the constraint of differential privacy (DP). We consider severa…
Anonymized Histograms in Intermediate Privacy Models
Badih Ghazi, Pritish Kamath, Ravi Kumar +1
We study the problem of privately computing the anonymized histogram (a.k.a. unattributed histogram), which is defined as the histogram without item labels. Previous works have pro…
Differentially Private All-Pairs Shortest Path Distances: Improved Algorithms and Lower Bounds
Badih Ghazi, Ravi Kumar, Pasin Manurangsi +1
We study the problem of releasing the weights of all-pair shortest paths in a weighted undirected graph with differential privacy (DP). In this setting, the underlying graph is fix…
Parsimonious Learning-Augmented Caching
Sungjin Im, Ravi Kumar, Aditya Petety +1
Learning-augmented algorithms -- in which, traditional algorithms are augmented with machine-learned predictions -- have emerged as a framework to go beyond worst-case analysis. Th…
Locally Private k-Means in One Round
Alisa Chang, Badih Ghazi, Ravi Kumar +1
We provide an approximation algorithm for k-means clustering in the one-round (aka non-interactive) local model of differential privacy (DP). This algorithm achieves an approximati…