Mark Bun's homepage

Mark Bun's homepage
Mark Bun
CDS 1021
665 Commonwealth Ave.
Boston, MA 02215
mbun [at] bu [dot] edu
I am an assistant professor in the
Department of Computer Science
at Boston University. Previously, I worked on
lower bounds
and
data privacy
as a Google Research Fellow at the
Simons Institute for the Theory of Computing
at UC Berkeley, and was a postdoctoral researcher in the
Theory of Computation Group
at Princeton University where I was hosted by
Mark Zhandry
. I completed my Ph.D. in
computer science
at Harvard University in 2016, where I was very fortunate to have
Salil Vadhan
as my advisor. As an undergraduate, I studied
math
and
computer science
at the University of Washington.
I am broadly interested in theoretical computer science, including data privacy, computational complexity, cryptography, and the foundations of machine learning. My current research focuses on
Using the methodologies of complexity theory to answer practically-motivated questions in
algorithmic data privacy
, and
Understanding the power of
real polynomial approximations
to Boolean functions and their applications in quantum computation, communication complexity, and learning theory.
BU e-resource access
Warning: If you receive the following
email
advertising a data collection research position, it is
not
from me.
Teaching
CS 332, Theory of Computation:
Spring 2025
Spring 2024
Fall 2022
Fall 2021
Spring 2021
Spring 2020
CS 391 B1, Responsible AI:
Fall 2025
CS 535, Complexity Theory:
Fall 2023
Fall 2020
CS 591 B1, Communication Complexity:
Fall 2019
CS 599 B1, Math for TCS:
Spring 2022
Research Papers
Maryam Aliakbarpour, Mark Bun, and Adam Smith.
Optimal Hypothesis Selection in (Almost) Linear Time
NeurIPS '24.
Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, and Steven Wu.
Oracle-Efficient Differentially Private Learning with Public Data
NeurIPS '24.
[arXiv]
Mark Bun, Marco Gaboardi, Marcel Neunhoffer, and Wanrong Zhang.
PODS '24.
Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections
[arXiv]
Mark Bun, Aloni Cohen, and Rathin Desai.
Private PAC Learning May be Harder than Online Learning
ALT '24 (Outstanding Paper Award), TPDP '24.
[arXiv]
Mark Bun, Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal.
Not All Learnable Distribution Classes are Privately Learnable
ALT '24.
[arXiv]
Maryam Aliakbarpour, Mark Bun, and Adam Smith.
Hypothesis Selection with Memory Constraints
NeurIPS '23.
[Full version]
Mark Bun and Nadezhda Voronova.
Approximate Degree Lower Bounds for Oracle Identification Problems
TQC '23.
[arXiv]
[ECCC]
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, and Jessica Sorrell.
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization
STOC '23, TPDP '23 (Contributed Talk), FORC '23.
[arXiv]
Shurong Lin, Mark Bun, Marco Gaboardi, Eric D. Kolaczyk, Adam Smith.
Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling
Electron. J. Statist. 18(1): 1455-1494 (2024).
[arXiv]
Mark Bun, Marco Gaboardi, and Ludmila Glinskih.
The Complexity of Verifying Boolean Programs as Differentially Private
CSF '22.
[arXiv]
Gavin Brown, Mark Bun, and Adam Smith.
Strong Memory Lower Bounds for Natural Learning Problems
COLT '22.
[arXiv]
Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, Jayshree Sarathy.
Controlling Privacy Loss in Sampling Schemes: an Analysis of Stratified and Cluster Sampling
FORC '22.
[arXiv]
Mark Bun, Marco Gaboardi, and Satchit Sivakumar.
Multiclass versus Binary Differentially Private PAC Learning
NeurIPS '21.
[arXiv]
Mark Bun, Marek Eliáš, and Janardhan Kulkarni.
Differentially Private Correlation Clustering
ICML '21.
[arXiv]
Gavin Brown, Mark Bun, Vitaly Feldman, Adam Smith, and Kunal Talwar.
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning?
STOC '21.
[arXiv]
Mark Bun.
A Computational Separation between Private Learning and Online Learning
NeurIPS '20.
[arXiv]
Mark Bun, Roi Livni, and Shay Moran.
An Equivalence between Private Classification and Online Prediction
FOCS '20 (Best Paper Award), TPDP '20 (Contributed Talk).
Part of J. ACM 69(4) 28:1-28:34, 2022 as "Private and Online Learnability Are Equivalent" (with N. Alon, R. Livni, M. Malliaris, and S. Moran).
[arXiv]
[TCS+]
Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, and Steven Wu.
New Oracle-Efficient Algorithms for Private Synthetic Data Release
ICML '20.
[arXiv]
Mark Bun, Marco L. Carmosino, and Jessica Sorrell.
Efficient, Noise-Tolerant, and Private Learning via Boosting
COLT '20.
[arXiv]
Mark Bun and Thomas Steinke.
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
NeurIPS '19.
[arXiv]
Mark Bun, Gautam Kamath, Thomas Steinke, and Steven Wu.
Private Hypothesis Selection
NeurIPS '19; TPDP '19 (Contributed Talk).
IEEE Trans. Inf. Theory 67(3): 1981-2000, 2021.
[arXiv]
Mark Bun and Justin Thaler.
The Large-Error Approximate Degree of AC
RANDOM '19.
Theory Comput. 17: 1-46, 2021 (special issue for APPROX-RANDOM '19).
[ECCC]
Mark Bun, Nikhil S. Mande, and Justin Thaler.
Sign-Rank Can Increase Under Intersection
ICALP '19.
[arXiv]
[ECCC]
Jarosław Błasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke.
Towards Instance-Optimal Private Query Release
SODA '19; TPDP '17.
[arXiv]
Mark Bun, Robin Kothari, and Justin Thaler.
Quantum Algorithms and Approximating Polynomials for Composed Functions with Shared Inputs
SODA '19.
Quantum 5: 543 (2021).
[arXiv]
[ECCC]
Mark Bun and Justin Thaler.
Approximate Degree and the Complexity of Depth-Three Circuits
RANDOM '18.
[ECCC]
Mark Bun, Cynthia Dwork, Guy N. Rothblum, and Thomas Steinke.
Composable and Versatile Privacy via Truncated CDP
STOC '18; TPDP '17.
Mark Bun, Robin Kothari, and Justin Thaler.
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
STOC '18, QIP '18 (Plenary Talk)
Theory of Computing 16(10):1-71, 2019 (special issue for STOC '18).
[arXiv]
[ECCC]
Mark Bun, Jelani Nelson, and Uri Stemmer.
Heavy Hitters and the Structure of Local Privacy
PODS '18.
ACM Trans. Algorithms 15(4): 51:1-51:40, 2019.
[arXiv]
K. Nissim, A. Bembenek, A. Wood, MB, M. Gaboardi, U. Gasser, D. R. O’Brien, T. Steinke, and S. Vadhan.
Bridging the Gap between Computer Science and Legal Approaches to Privacy
Harvard J. of Law & Tech. 31(2): 687-780, 2018.
2019 PET Caspar Bowden Award for Outstanding Research in Privacy Enhancing Technologies.
[JOLT]
Mark Bun and Justin Thaler.
A Nearly Optimal Bound on the Approximate Degree of AC
FOCS '17.
SIAM J. Comput., 49(4):FOCS17-59-FOCS17-96, 2019 (special issue for FOCS '17).
[arXiv]
[ECCC]
[slides]
Marko Mitrovic, Mark Bun, Andreas Krause, and Amin Karbasi.
Differentially Private Submodular Maximization: Data Summarization in Disguise
ICML '17.
[PMLR]
Mark Bun, Thomas Steinke, and Jonathan Ullman.
Make Up Your Mind: The Price of Online Queries in Differential Privacy
SODA '17; TPDP '16 (Contributed Talk).
J. Pri. Confidentiality, 9(1), 2019 (special issue for TPDP '16).
[arXiv]
[slides]
Mark Bun, Yi-Hsiu Chen, and Salil Vadhan.
Separating Computational and Statistical Differential Privacy in the Client-Server Model
TCC '16-B.
[ePrint]
Mark Bun and Thomas Steinke.
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
TCC '16-B.
[arXiv]
Mark Bun and Justin Thaler.
Dual Polynomials for Collision and Element Distinctness
Theory of Computing, 12(16):1-34, 2016.
[ToC]
[arXiv]
[ECCC]
Mark Bun and Justin Thaler.
Improved Bounds on the Sign-Rank of AC
ICALP '16.
[ECCC]
Mark Bun, Kobbi Nissim, and Uri Stemmer.
Simultaneous Private Learning of Multiple Concepts
ITCS '16.
J. Mach. Learn. Res. 20(94):1−34, 2019.
[arXiv]
[slides]
Mark Bun and Mark Zhandry.
Order-Revealing Encryption and the Hardness of Private Learning
TCC '16-A.
[arXiv]
[ePrint]
[slides]
Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil Vadhan.
Differentially Private Release and Learning of Threshold Functions
FOCS '15.
[arXiv]
[slides]
Mark Bun and Thomas Steinke.
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness
RANDOM '15.
[arXiv]
[ECCC]
[slides]
Mark Bun and Justin Thaler.
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
ICALP '15.
[arXiv]
[ECCC]
[slides]
Mark Bun, Jonathan Ullman, and Salil Vadhan.
Fingerprinting Codes and the Price of Approximate Differential Privacy
STOC '14.
SIAM J. Comput. 47(5): 1888-1938, 2018 (special issue for STOC '14).
[arXiv]
[slides]
Mark Bun and Justin Thaler.
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities
ICALP '13, Best Paper Award for Track A.
Information and Computation 243:2-25, 2015 (special issue for ICALP '13).
[arXiv]
[ECCC]
[slides]
Other Manuscripts
Mark Bun and Justin Thaler.
Approximate Degree in Classical and Quantum Computing
Foundations and Trends in Theoretical Computer Science, December 2022
[now publishers]
[latest revision]
Mark Bun and Justin Thaler.
Approximate Degree in Classical and Quantum Computing
ACM SIGACT News 51(4):48-72, December 2020
[ACM]
A. Wood, M. Altman, A. Bembenek, MB, M. Gaboardi, J. Honaker, K. Nissim, D. R. O’Brien, T. Steinke, and S. Vadhan.
Differential Privacy: A Primer for a Non-Technical Audience
Vanderbilt J. of Ent. & Tech. Law 21(17):209-276, 2018
[SSRN]
Ph.D. Thesis.
New Separations in the Complexity of Differential Privacy
July 2016.
[DASH]
Current PhD Students
Rathin Desai
Mandar Juvekar
(co-advised with Adam Smith)
Satchit Sivakumar
Nadezhda (Nadya) Voronova
Graduated PhD Students
Ludmila Glinskih
(co-advised with Sofya Raskhodnikova), now Software Engineer at Google
Past Postdocs
Marco Carmosino
CI Fellow 2020-21, now Research Scientist at IBM
Professional Activities
Co-Organizer of:
Boston Differential Privacy Summer School, 2022
Mathematical Foundations of Data Privacy @ Banff International Research Station, 2018
Program Committee Member of:
SOSA 2024
ESA 2023
TPDP 2023
STOC 2023
TPDP 2022
NeurIPS 2021
(Area Chair)
TCC 2021
ITC 2021
FORC 2021
PPAI 2021
TPDP 2020
STOC 2020
SODA 2020
PriML 2019
TPDP 2019
CRYPTO 2019
ISAAC 2018
TPDP 2018
Reviewer for:
NeurIPS 2023
COLT 2022
COLT 2021
AISTATS 2021
NeurIPS 2020
NeurIPS 2018
This page last updated: January 2024