73 citations · 585 across the 58 of their papers we have counts for
26 papers · 1 filter
Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization
Aleksandar Nikolov, Haohua Tang, Jonathan Ullman
In this paper we consider several related online computation problems. First, we study answering sequences of statistical queries arriving online, and being answered immediately wh…
Differentially Private Medians and Interior Points for Non-Pathological Data
Maryam Aliakbarpour, Rose Silver, Thomas Steinke +1
We construct differentially private estimators with low sample complexity that estimate the median of an arbitrary distribution over satisfying very mild moment condit…
Fair and Optimal Cohort Selection for Linear Utilities
Konstantina Bairaktari, Huy Le Nguyen, Jonathan Ullman
The rise of algorithmic decision-making has created an explosion of research around the fairness of those algorithms. While there are many compelling notions of individual fairness…
The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation
Albert Cheu, Jonathan Ullman
There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the…
Fair and Useful Cohort Selection
Konstantina Bairaktari, Paul Langton, Huy L. Nguyen +2
A challenge in fair algorithm design is that, while there are compelling notions of individual fairness, these notions typically do not satisfy desirable composition properties, an…
Private Mean Estimation of Heavy-Tailed Distributions
Gautam Kamath, Vikrant Singhal, Jonathan Ullman
We give new upper and lower bounds on the minimax sample complexity of differentially private mean estimation of distributions with bounded -th moments. Roughly speaking, in the…