Mark Bun

activity

20152021

most citedAverage-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation

22 citations · 59 across the 11 of their papers we have counts for

collaborators

Showing 2017Show all

2 papers · 1 filter

cs.DS2017★ 5 cited

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…

cs.CC2017

A Nearly Optimal Lower Bound on the Approximate Degree of AC $^{0}$

Mark Bun, Justin Thaler

The approximate degree of a Boolean function $f : {- 1, 1}^{n} \to {- 1, 1}$ is the least degree of a real polynomial that approximates $f$ pointwise to error at most…

Heavy Hitters and the Structure of Local Privacy

A Nearly Optimal Lower Bound on the Approximate Degree of AC0

A Nearly Optimal Lower Bound on the Approximate Degree of AC $^{0}$