Mark Bun
3 papers in the PaperMetrix corpus
Papers by this author
-
Average-Case Averages: Private Algorithms for Smooth Sensitivity and\n Mean Estimation
2019 · arXiv (Cornell University)
The simplest and most widely applied method for guaranteeing differential\nprivacy is to add instance-independent noise to a statistic of interest that is\nscaled to its global sensitivity. However, global sensitivity is a worst-case\nnotion that is often …
-
New Oracle-Efficient Algorithms for Private Synthetic Data Release
2020 · arXiv (Cornell University)
We present three new algorithms for constructing differentially private synthetic data---a sanitized version of a sensitive dataset that approximately preserves the answers to a large collection of statistical queries. All three algorithms are \emph{oracle-efficient} in …
-
A Computational Separation between Private Learning and Online Learning
2020 · arXiv (Cornell University)
A recent line of work has shown a qualitative equivalence between differentially private PAC learning and online learning: A concept class is privately learnable if and only if it is online learnable with a finite …