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

1. Using the methodologies of complexity theory to answer practically-motivated questions in algorithmic data privacy, and

2. 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

Teaching

---

CS 332, Theory of Computation: Fall 2022 Fall 2021 Spring 2021 Spring 2020

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

---

• Mark Bun, Marco Gaboardi, Marcel Neunhoffer, and Wanrong Zhang.
  Continual Release of Differentially Private Synthetic Data.
  [arXiv]

• 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.
  [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

Ludmila Glinskih (co-advised with Sofya Raskhodnikova)

Mandar Juvekar (co-advised with Adam Smith)

Satchit Sivakumar

Nadezhda (Nadya) Voronova

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: October 2023