papers
Publications (14)
cs.CC2014
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
Mark Bun, Justin Thaler
cs.CC2015
Dual Polynomials for Collision and Element Distinctness
Mark Bun, Justin Thaler
cs.CC2014
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Mark Bun, Justin Thaler
cs.CR2018
Fingerprinting Codes and the Price of Approximate Differential Privacy
Mark Bun, Jonathan Ullman, Salil Vadhan
cs.CC2019
Sign-Rank Can Increase Under Intersection
Mark Bun, Nikhil S. Mande, Justin Thaler
cs.CR2015
Order-Revealing Encryption and the Hardness of Private Learning
Mark Bun, Mark Zhandry
cs.CC2017
A Nearly Optimal Lower Bound on the Approximate Degree of AC$^0$
Mark Bun, Justin Thaler
cs.CR2016
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
Mark Bun, Thomas Steinke
cs.DS2018
Towards Instance-Optimal Private Query Release
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov +1
cs.DS2017
Heavy Hitters and the Structure of Local Privacy
Mark Bun, Jelani Nelson, Uri Stemmer
cs.DS2015
Simultaneous Private Learning of Multiple Concepts
Mark Bun, Kobbi Nissim, Uri Stemmer
math.ST2019
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
Mark Bun, Thomas Steinke
cs.CC2014
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
Mark Bun, Thomas Steinke
cs.CR2016
Make Up Your Mind: The Price of Online Queries in Differential Privacy
Mark Bun, Thomas Steinke, Jonathan Ullman