research
∙
05/24/2023
Adaptive Data Analysis in a Balanced Adversarial Model
In adaptive data analysis, a mechanism gets n i.i.d. samples from an unk...
share
research
∙
05/16/2023
Private Everlasting Prediction
A private learner is trained on a sample of labeled points and generates...
research
∙
02/27/2023
On Differentially Private Online Predictions
In this work we introduce an interactive variant of joint differential p...
research
∙
02/11/2023
On Differential Privacy and Adaptive Data Analysis with Bounded Space
We study the space complexity of the two related fields of differential ...
research
∙
01/29/2023
Concurrent Shuffle Differential Privacy Under Continual Observation
We introduce the concurrent shuffle model of differential privacy. In th...
research
∙
01/22/2023
Relaxed Models for Adversarial Streaming: The Advice Model and the Bounded Interruptions Model
Streaming algorithms are typically analyzed in the oblivious setting, wh...
research
∙
11/22/2022
Generalized Private Selection and Testing with High Confidence
Composition theorems are general and powerful tools that facilitate priv...
research
∙
11/11/2022
Õptimal Differentially Private Learning of Thresholds and Quasi-Concave Optimization
The problem of learning threshold functions is a fundamental one in mach...
research
∙
07/11/2022
MPC for Tech Giants (GMPC): Enabling Gulliver and the Lilliputians to Cooperate Amicably
In this work, we introduce the Gulliver multi-party computation model (G...
research
∙
07/03/2022
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
CountSketch and Feature Hashing (the "hashing trick") are popular random...
research
∙
02/28/2022
On the Robustness of CountSketch to Adaptive Inputs
CountSketch is a popular dimensionality reduction technique that maps ve...
research
∙
02/10/2022
Monotone Learning
The amount of training-data is one of the key factors which determines t...
research
∙
12/29/2021
Differentially-Private Clustering of Easy Instances
Clustering is a fundamental problem in data analysis. In differentially ...
research
∙
11/26/2021
A Note on Sanitizing Streams with Differential Privacy
The literature on data sanitization aims to design algorithms that take ...
research
∙
11/07/2021
Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds
A dynamic algorithm against an adaptive adversary is required to be corr...
research
∙
10/19/2021
FriendlyCore: Practical Differentially Private Aggregation
Differentially private algorithms for common metric aggregation tasks, s...
research
∙
10/11/2021
Differentially Private Approximate Quantiles
In this work we study the problem of differentially private (DP) quantil...
research
∙
07/30/2021
A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators
Streaming algorithms are algorithms for processing large data streams, u...
research
∙
07/24/2021
On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
We revisit the fundamental problem of learning Axis-Aligned-Rectangles o...
research
∙
06/05/2021
Differentially Private Multi-Armed Bandits in the Shuffle Model
We give an (ε,δ)-differentially private algorithm for the multi-armed ba...
research
∙
01/26/2021
Separating Adaptive Streaming from Oblivious Streaming
We present a streaming problem for which every adversarially-robust stre...
research
∙
10/25/2020
Differentially Private Weighted Sampling
Common datasets have the form of elements with keys (e.g., transactions ...
research
∙
10/02/2020
The Sparse Vector Technique, Revisited
We revisit one of the most basic and widely applicable techniques in the...
research
∙
09/28/2020
On the Round Complexity of the Shuffle Model
The shuffle model of differential privacy was proposed as a viable model...
research
∙
04/16/2020
Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
We present a differentially private learner for halfspaces over a finite...
research
∙
04/13/2020
Adversarially Robust Streaming Algorithms via Differential Privacy
A streaming algorithm is said to be adversarially robust if its accuracy...
research
∙
03/30/2020
How to Find a Point in the Convex Hull Privately
We study the question of how to compute a point in the convex hull of an...
research
∙
03/10/2020
Closure Properties for Private Classification and Online Prediction
Let H be a class of boolean functions and consider acomposed class H' th...
research
∙
12/18/2019
The power of synergy in differential privacy:Combining a small curator with local randomizers
Motivated by the desire to bridge the utility gap between local and trus...
research
∙
11/22/2019
Privately Learning Thresholds: Closing the Exponential Gap
We study the sample complexity of learning threshold functions under the...
research
∙
07/04/2019
Locally Private k-Means Clustering
We design a new algorithm for the Euclidean k-means problem that operate...
research
∙
02/27/2019
Private Center Points and Learning of Halfspaces
We present a private learner for halfspaces over an arbitrary finite dom...
research
∙
02/13/2019
Differentially Private Learning of Geometric Concepts
We present differentially private efficient algorithms for learning unio...
research
∙
06/15/2018
The Limits of Post-Selection Generalization
While statistics and machine learning offers numerous methods for ensuri...
research
∙
04/21/2018
Differentially Private k-Means with Constant Multiplicative Error
We design new differentially private algorithms for the Euclidean k-mean...
research
∙
11/13/2017
Heavy Hitters and the Structure of Local Privacy
We present a new locally differentially private algorithm for the heavy ...
research
∙
07/10/2014