1.7k citations · 3.3k across the 42 of their papers we have counts for
50 papers
Triangle Counting with Local Edge Differential Privacy
Talya Eden, Quanquan C. Liu, Sofya Raskhodnikova +1
Many deployments of differential privacy in industry are in the local model, where each party releases its private information via a differentially private randomizer. We study tri…
Node-Differentially Private Estimation of the Number of Connected Components
Iden Kalemaj, Sofya Raskhodnikova, Adam Smith +1
We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an -vertex graph and…
Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions
Gavin Brown, Samuel B. Hopkins, Adam Smith
We present a fast, differentially private algorithm for high-dimensional covariance-aware mean estimation with nearly optimal sample complexity. Only exponential-time estimators we…
Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling
Shurong Lin, Mark Bun, Marco Gaboardi +2
Confidence intervals are a fundamental tool for quantifying the uncertainty of parameters of interest. With the increase of data privacy awareness, developing a private version of…
Differentially Private Sampling from Distributions
Sofya Raskhodnikova, Satchit Sivakumar, Adam Smith +1
We initiate an investigation of private sampling from distributions. Given a dataset with independent observations from an unknown distribution , a sampling algorithm must o…
Instance-Optimal Differentially Private Estimation
Audra McMillan, Adam Smith, Jon Ullman
In this work, we study local minimax convergence estimation rates subject to -differential privacy. Unlike worst-case rates, which may be conservative, algorithms that are local…