65 citations · 177 across the 68 of their papers we have counts for
20 papers · 1 filter
Online Differentially Private Consistent Clustering
Edith Cohen, Vadym Doroshenko, Badih Ghazi +7
We study differentially private (DP) -means and -median clustering in the online streaming setting. In this model, points arrive sequentially, and at each time step, we need…
Fixed-Parameter Tractability of Private Synthetic Data Generation
Badih Ghazi, Cristóbal Guzmán, Pritish Kamath +3
We study the problem of generating synthetic data under differential privacy. We establish fixed-parameter tractability (FPT) for this problem where the parameter is the treewidth…
Convex Optimization with Local Label Differential Privacy: Tight Bounds in All Privacy Regimes
Lynn Chua, Badih Ghazi, Ravi Kumar +3
We study the problem of Stochastic Convex Optimization (SCO) under the constraint of local Label Differential Privacy (L-LDP). In this setting, the features are considered public,…
On Computing Pairwise Statistics with Local Differential Privacy
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
We study the problem of computing pairwise statistics, i.e., ones of the form , where denotes the input to the th user, with…
Individualized Privacy Accounting via Subsampling with Applications in Combinatorial Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
In this work, we give a new technique for analyzing individualized privacy accounting via the following simple observation: if an algorithm is one-sided add-DP, then its subsampled…
User-Level Differential Privacy With Few Examples Per User
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS 2021, Bun et al. STOC 2023] obtained generic algorithms that work for various learning tasks. However, t…
Optimizing Hierarchical Queries for the Attribution Reporting API
Matthew Dawson, Badih Ghazi, Pritish Kamath +8
We study the task of performing hierarchical queries based on summary reports from the {\em Attribution Reporting API} for ad conversion measurement. We demonstrate that methods fr…
On Differentially Private Sampling from Gaussian and Product Distributions
Badih Ghazi, Xiao Hu, Ravi Kumar +1
Given a dataset of i.i.d. samples from an unknown distribution , we consider the problem of generating a sample from a distribution that is close to in total variation d…
Pure-DP Aggregation in the Shuffle Model: Error-Optimal and Communication-Efficient
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
We obtain a new protocol for binary counting in the -shuffle-DP model with error and expected communication $\tilde{O}\left(\frac{\log n}{\varepsilo…
On Differentially Private Counting on Trees
Badih Ghazi, Pritish Kamath, Ravi Kumar +2
We study the problem of performing counting queries at different levels in hierarchical structures while preserving individuals' privacy. Motivated by applications, we propose a ne…
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…
Faster Privacy Accounting via Evolving Discretization
Badih Ghazi, Pritish Kamath, Ravi Kumar +1
We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for composition of mechanisms.…
Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions
Vadym Doroshenko, Badih Ghazi, Pritish Kamath +2
The privacy loss distribution (PLD) provides a tight characterization of the privacy loss of a mechanism in the context of differential privacy (DP). Recent work has shown that PLD…
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…
Private Rank Aggregation in Central and Local Models
Daniel Alabi, Badih Ghazi, Ravi Kumar +1
In social choice theory, (Kemeny) rank aggregation is a well-studied problem where the goal is to combine rankings from multiple voters into a single ranking on the same set of ite…
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…
On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
In this work, we study the problem of answering queries with -differential privacy, where each query has sensitivity one. We give an algorithm for this task that achiev…
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk +3
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid. Our algorithms are analyzed f…