research
∙
09/08/2023
The Complexity of Verifying Boolean Programs as Differentially Private
We study the complexity of the problem of verifying differential privacy...
share
research
∙
06/13/2023
Continual Release of Differentially Private Synthetic Data
Motivated by privacy concerns in long-term longitudinal studies in medic...
research
∙
03/22/2023
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
The notion of replicable algorithms was introduced in Impagliazzo et al....
research
∙
03/07/2023
Approximate degree lower bounds for oracle identification problems
The approximate degree of a Boolean function is the minimum degree of re...
research
∙
06/09/2022
Strong Memory Lower Bounds for Learning Natural Models
We give lower bounds on the amount of memory required by one-pass stream...
research
∙
07/22/2021
Multiclass versus Binary Differentially Private PAC Learning
We show a generic reduction from multiclass differentially private PAC l...
research
∙
02/17/2021
Differentially Private Correlation Clustering
Correlation clustering is a widely used technique in unsupervised machin...
research
∙
12/11/2020
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
Modern machine learning models are complex and frequently encode surpris...
research
∙
07/24/2020
Controlling Privacy Loss in Survey Sampling (Working Paper)
Social science and economics research is often based on data collected i...
research
∙
07/11/2020
A Computational Separation between Private Learning and Online Learning
A recent line of work has shown a qualitative equivalence between differ...
research
∙
07/10/2020
New Oracle-Efficient Algorithms for Private Synthetic Data Release
We present three new algorithms for constructing differentially private ...
research
∙
03/01/2020
An Equivalence Between Private Classification and Online Prediction
We prove that every concept class with finite Littlestone dimension can ...
research
∙
02/04/2020
Efficient, Noise-Tolerant, and Private Learning via Boosting
We introduce a simple framework for designing private boosting algorithm...
research
∙
06/06/2019
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
The simplest and most widely applied method for guaranteeing differentia...
research
∙
05/30/2019
Private Hypothesis Selection
We provide a differentially private algorithm for hypothesis selection. ...
research
∙
03/01/2019
Sign-Rank Can Increase Under Intersection
The communication class UPP^cc is a communication analog of the Turing M...
research
∙
11/09/2018
Towards Instance-Optimal Private Query Release
We study efficient mechanisms for the query release problem in different...
research
∙
09/06/2018
Quantum algorithms and approximating polynomials for composed functions with shared inputs
We give new quantum algorithms for evaluating composed functions whose i...
research
∙
11/13/2017
Heavy Hitters and the Structure of Local Privacy
We present a new locally differentially private algorithm for the heavy ...
research
∙
10/25/2017