
Multiclass versus Binary Differentially Private PAC Learning
We show a generic reduction from multiclass differentially private PAC l...
read it

Differentially Private Correlation Clustering
Correlation clustering is a widely used technique in unsupervised machin...
read it

When is Memorization of Irrelevant Training Data Necessary for HighAccuracy Learning?
Modern machine learning models are complex and frequently encode surpris...
read it

Controlling Privacy Loss in Survey Sampling (Working Paper)
Social science and economics research is often based on data collected i...
read it

A Computational Separation between Private Learning and Online Learning
A recent line of work has shown a qualitative equivalence between differ...
read it

New OracleEfficient Algorithms for Private Synthetic Data Release
We present three new algorithms for constructing differentially private ...
read it

An Equivalence Between Private Classification and Online Prediction
We prove that every concept class with finite Littlestone dimension can ...
read it

Efficient, NoiseTolerant, and Private Learning via Boosting
We introduce a simple framework for designing private boosting algorithm...
read it

AverageCase Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
The simplest and most widely applied method for guaranteeing differentia...
read it

Private Hypothesis Selection
We provide a differentially private algorithm for hypothesis selection. ...
read it

SignRank Can Increase Under Intersection
The communication class UPP^cc is a communication analog of the Turing M...
read it

Towards InstanceOptimal Private Query Release
We study efficient mechanisms for the query release problem in different...
read it

Quantum algorithms and approximating polynomials for composed functions with shared inputs
We give new quantum algorithms for evaluating composed functions whose i...
read it

Heavy Hitters and the Structure of Local Privacy
We present a new locally differentially private algorithm for the heavy ...
read it

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
The approximate degree of a Boolean function f is the least degree of a ...
read it
Mark Bun
is this you? claim profile