65 citations · 230 across the 37 of their papers we have counts for
Showing 2013Show all
3 papers · 1 filter
cs.CR2013★ 4 cited
Fingerprinting Codes and the Price of Approximate Differential Privacy
Mark Bun, Jonathan Ullman, Salil Vadhan
We show new lower bounds on the sample complexity of -differentially private algorithms that accurately answer large sets of counting queries. A counting query on…
cs.CC2013★ 3 cited
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Mark Bun, Justin Thaler
We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit can…
cs.CC2013
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
Mark Bun, Justin Thaler
The -approximate degree of a Boolean function is the minimum degree of a real polynomial that approximates to within in the …