Mark Bun

According to our database, Mark Bun authored at least 47 papers between 2013 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Private PAC Learning May be Harder than Online Learning.

Mark Bun, Aloni Cohen, Rathin Desai

CoRR, 2024

Oracle-Efficient Differentially Private Learning with Public Data.

Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, Steven Wu

CoRR, 2024

Not All Learnable Distribution Classes are Privately Learnable.

Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal

CoRR, 2024

2023

Approximate degree lower bounds for oracle identification problems.

Mark Bun, Nadezhda Voronova

Electron. Colloquium Comput. Complex., 2023

Continual Release of Differentially Private Synthetic Data.

Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, Wanrong Zhang

CoRR, 2023

Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling.

Shurong Lin, Mark Bun, Marco Gaboardi, Eric D. Kolaczyk, Adam Smith

CoRR, 2023

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.

Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Hypothesis Selection with Memory Constraints.

Maryam Aliakbarpour, Mark Bun, Adam Smith

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

Private and Online Learnability Are Equivalent.

Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran

J. ACM, 2022

Approximate Degree in Classical and Quantum Computing.

Mark Bun, Justin Thaler

Found. Trends Theor. Comput. Sci., 2022

Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling.

Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, Jayshree Sarathy

Proceedings of the 3rd Symposium on Foundations of Responsible Computing, 2022

The Complexity of Verifying Boolean Programs as Differentially Private.

Mark Bun, Marco Gaboardi, Ludmila Glinskih

Proceedings of the 35th IEEE Computer Security Foundations Symposium, 2022

Strong Memory Lower Bounds for Learning Natural Models.

Gavin Brown, Mark Bun, Adam D. Smith

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

The Large-Error Approximate Degree of AC⁰.

Mark Bun, Justin Thaler

Theory Comput., 2021

Private Hypothesis Selection.

Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu

IEEE Trans. Inf. Theory, 2021

When is memorization of irrelevant training data necessary for high-accuracy learning?

Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Multiclass versus Binary Differentially Private PAC Learning.

Satchit Sivakumar, Mark Bun, Marco Gaboardi

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Differentially Private Correlation Clustering.

Mark Bun, Marek Eliás, Janardhan Kulkarni

Proceedings of the 38th International Conference on Machine Learning, 2021

2020

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.

Mark Bun, Robin Kothari, Justin Thaler

Theory Comput., 2020

Guest Column: Approximate Degree in Classical and Quantum Computing.

Mark Bun, Justin Thaler

SIGACT News, 2020

Controlling Privacy Loss in Survey Sampling (Working Paper).

Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan

CoRR, 2020

A Computational Separation between Private Learning and Online Learning.

Mark Bun

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

New Oracle-Efficient Algorithms for Private Synthetic Data Release.

Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu

Proceedings of the 37th International Conference on Machine Learning, 2020

An Equivalence Between Private Classification and Online Prediction.

Mark Bun, Roi Livni, Shay Moran

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Efficient, Noise-Tolerant, and Private Learning via Boosting.

Mark Bun, Marco Leandro Carmosino, Jessica Sorrell

Proceedings of the Conference on Learning Theory, 2020

2019

Heavy Hitters and the Structure of Local Privacy.

Mark Bun, Jelani Nelson, Uri Stemmer

ACM Trans. Algorithms, 2019

Make Up Your Mind: The Price of Online Queries in Differential Privacy.

Mark Bun, Thomas Steinke, Jonathan R. Ullman

J. Priv. Confidentiality, 2019

Simultaneous Private Learning of Multiple Concepts.

Mark Bun, Kobbi Nissim, Uri Stemmer

J. Mach. Learn. Res., 2019

Sign-Rank Can Increase Under Intersection.

Mark Bun, Nikhil S. Mande, Justin Thaler

Electron. Colloquium Comput. Complex., 2019

Towards Instance-Optimal Private Query Release.

Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation.

Mark Bun, Thomas Steinke

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Fingerprinting Codes and the Price of Approximate Differential Privacy.

Mark Bun, Jonathan R. Ullman, Salil P. Vadhan

SIAM J. Comput., 2018

Quantum algorithms and approximating polynomials for composed functions with shared inputs.

Mark Bun, Robin Kothari, Justin Thaler

Electron. Colloquium Comput. Complex., 2018

Composable and versatile privacy via truncated CDP.

Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

A Nearly Optimal Lower Bound on the Approximate Degree of AC⁰.

Mark Bun, Justin Thaler

Electron. Colloquium Comput. Complex., 2017

Differentially Private Submodular Maximization: Data Summarization in Disguise.

Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi

Proceedings of the 34th International Conference on Machine Learning, 2017

2016

Dual Polynomials for Collision and Element Distinctness.

Mark Bun, Justin Thaler

Theory Comput., 2016

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds.

Mark Bun, Thomas Steinke

IACR Cryptol. ePrint Arch., 2016

Separating Computational and Statistical Differential Privacy in the Client-Server Model.

Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan

IACR Cryptol. ePrint Arch., 2016

Approximate Degree and the Complexity of Depth Three Circuits.

Mark Bun, Justin Thaler

Electron. Colloquium Comput. Complex., 2016

Improved Bounds on the Sign-Rank of AC⁰.

Mark Bun, Justin Thaler

Electron. Colloquium Comput. Complex., 2016

Improved Bounds on the Sign-Rank of AC^0.

Mark Bun, Justin Thaler

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Order-Revealing Encryption and the Hardness of Private Learning.

Mark Bun, Mark Zhandry

IACR Cryptol. ePrint Arch., 2015

Differentially Private Release and Learning of Threshold Functions.

Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness.

Mark Bun, Thomas Steinke

Electron. Colloquium Comput. Complex., 2014

2013

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits.

Mark Bun, Justin Thaler

Electron. Colloquium Comput. Complex., 2013

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.

Mark Bun, Justin Thaler

Electron. Colloquium Comput. Complex., 2013