5 citations · 8 across the 4 of their papers we have counts for
6 papers
Heavy Hitters and the Structure of Local Privacy
Mark Bun, Jelani Nelson, Uri Stemmer
We present a new locally differentially private algorithm for the heavy hitters problem which achieves optimal worst-case error as a function of all standardly considered parameter…
A Nearly Optimal Lower Bound on the Approximate Degree of AC
Mark Bun, Justin Thaler
The approximate degree of a Boolean function is the least degree of a real polynomial that approximates pointwise to error at most…
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
Mark Bun, Thomas Steinke
"Concentrated differential privacy" was recently introduced by Dwork and Rothblum as a relaxation of differential privacy, which permits sharper analyses of many privacy-preserving…
Make Up Your Mind: The Price of Online Queries in Differential Privacy
Mark Bun, Thomas Steinke, Jonathan Ullman
We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set Q of allowable que…
Order-Revealing Encryption and the Hardness of Private Learning
Mark Bun, Mark Zhandry
An order-revealing encryption scheme gives a public procedure by which two ciphertexts can be compared to reveal the ordering of their underlying plaintexts. We show how to use ord…
Dual Polynomials for Collision and Element Distinctness
Mark Bun, Justin Thaler
The approximate degree of a Boolean function is the minimum degree of a real polynomial that approximates to within error in the $\ell_\inf…