Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. - Mark Bun; Justin Thaler (Electron. Colloquium Comput. Complex., 2013)

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. - Mark Bun; Justin Thaler (Electron. Colloquium Comput. Complex., 2013)

Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. - Mark Bun; Thomas Steinke 002 (Electron. Colloquium Comput. Complex., 2014)

Differentially Private Release and Learning of Threshold Functions. - Mark Bun; Kobbi Nissim; Uri Stemmer; Salil P. Vadhan (FOCS, 2015)

Dual Polynomials for Collision and Element Distinctness. - Mark Bun; Justin Thaler (Electron. Colloquium Comput. Complex., 2015)

Order-Revealing Encryption and the Hardness of Private Learning. - Mark Bun; Mark Zhandry (IACR Cryptol. ePrint Arch., 2015)

Improved Bounds on the Sign-Rank of AC^0. - Mark Bun; Justin Thaler (ICALP, 2016)

Improved Bounds on the Sign-Rank of AC0. - Mark Bun; Justin Thaler (Electron. Colloquium Comput. Complex., 2016)

Approximate Degree and the Complexity of Depth Three Circuits. - Mark Bun; Justin Thaler (Electron. Colloquium Comput. Complex., 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)

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. - Mark Bun; Thomas Steinke 002 (IACR Cryptol. ePrint Arch., 2016)

Differentially Private Submodular Maximization: Data Summarization in Disguise. - Marko Mitrovic; Mark Bun; Andreas Krause 001; Amin Karbasi (ICML, 2017)

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. - Mark Bun; Robin Kothari; Justin Thaler (Electron. Colloquium Comput. Complex., 2017)

Composable and versatile privacy via truncated CDP. - Mark Bun; Cynthia Dwork; Guy N. Rothblum; Thomas Steinke 002 (STOC, 2018)

The Large-Error Approximate Degree of AC0. - Mark Bun; Justin Thaler (Electron. Colloquium Comput. Complex., 2018)

Fingerprinting Codes and the Price of Approximate Differential Privacy. - Mark Bun; Jonathan R. Ullman; Salil P. Vadhan (SIAM J. Comput., 2018)

Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. - Mark Bun; Thomas Steinke 002 (NeurIPS, 2019)

Towards Instance-Optimal Private Query Release. - Jaroslaw Blasiok; Mark Bun; Aleksandar Nikolov; Thomas Steinke 002 (SODA, 2019)

Sign-Rank Can Increase Under Intersection. - Mark Bun; Nikhil S. Mande; Justin Thaler (Electron. Colloquium Comput. Complex., 2019)

Simultaneous Private Learning of Multiple Concepts. - Mark Bun; Kobbi Nissim; Uri Stemmer (J. Mach. Learn. Res., 2019)

Make Up Your Mind: The Price of Online Queries in Differential Privacy. - Mark Bun; Thomas Steinke 002; Jonathan R. Ullman (J. Priv. Confidentiality, 2019)

Heavy Hitters and the Structure of Local Privacy. - Mark Bun; Jelani Nelson; Uri Stemmer (ACM Trans. Algorithms, 2019)

Efficient, Noise-Tolerant, and Private Learning via Boosting. - Mark Bun; Marco Leandro Carmosino; Jessica Sorrell (COLT, 2020)

An Equivalence Between Private Classification and Online Prediction. - Mark Bun; Roi Livni; Shay Moran (FOCS, 2020)

New Oracle-Efficient Algorithms for Private Synthetic Data Release. - Giuseppe Vietri; Grace Tian; Mark Bun; Thomas Steinke 002; Zhiwei Steven Wu (ICML, 2020)

A Computational Separation between Private Learning and Online Learning. - Mark Bun (NeurIPS, 2020)

Controlling Privacy Loss in Survey Sampling (Working Paper). - Mark Bun; Jörg Drechsler; Marco Gaboardi; Audra McMillan (CoRR, 2020)

A Nearly Optimal Lower Bound on the Approximate Degree of AC0. - Mark Bun; Justin Thaler (SIAM J. Comput., 2020)

Guest Column: Approximate Degree in Classical and Quantum Computing. - Mark Bun; Justin Thaler (SIGACT News, 2020)

Differentially Private Correlation Clustering. - Mark Bun; Marek Eliás 001; Janardhan Kulkarni (ICML, 2021)

Multiclass versus Binary Differentially Private PAC Learning. - Satchit Sivakumar; Mark Bun; Marco Gaboardi (NeurIPS, 2021)

When is memorization of irrelevant training data necessary for high-accuracy learning? - Gavin Brown 003; Mark Bun; Vitaly Feldman; Adam D. Smith 001; Kunal Talwar (STOC, 2021)

Quantum algorithms and approximating polynomials for composed functions with shared inputs. - Mark Bun; Robin Kothari; Justin Thaler (Quantum, 2021)

Private Hypothesis Selection. - Mark Bun; Gautam Kamath 001; Thomas Steinke 002; Zhiwei Steven Wu (IEEE Trans. Inf. Theory, 2021)

Strong Memory Lower Bounds for Learning Natural Models. - Gavin Brown 003; Mark Bun; Adam D. Smith 001 (COLT, 2022)

The Complexity of Verifying Boolean Programs as Differentially Private. - Mark Bun; Marco Gaboardi; Ludmila Glinskih (CSF, 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 (FORC, 2022)

Approximate Degree in Classical and Quantum Computing. - Mark Bun; Justin Thaler (Found. Trends Theor. Comput. Sci., 2022)

Private and Online Learnability Are Equivalent. - Noga Alon; Mark Bun; Roi Livni; Maryanthe Malliaris; Shay Moran (J. ACM, 2022)

Hypothesis Selection with Memory Constraints. - Maryam Aliakbarpour; Mark Bun; Adam Smith 006 (NeurIPS, 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 (STOC, 2023)

Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling. - Shurong Lin; Mark Bun; Marco Gaboardi; Eric D. Kolaczyk; Adam Smith 006 (CoRR, 2023)

Continual Release of Differentially Private Synthetic Data. - Mark Bun; Marco Gaboardi; Marcel Neunhoeffer; Wanrong Zhang 001 (CoRR, 2023)

Approximate degree lower bounds for oracle identification problems. - Mark Bun; Nadezhda Voronova (Electron. Colloquium Comput. Complex., 2023)

Not All Learnable Distribution Classes are Privately Learnable. - Mark Bun; Gautam Kamath 001; Argyris Mouzakis; Vikrant Singhal (ALT, 2024)

Private PAC Learning May be Harder than Online Learning. - Mark Bun; Aloni Cohen; Rathin Desai (ALT, 2024)

Optimal Hypothesis Selection in (Almost) Linear Time. - Maryam Aliakbarpour; Mark Bun; Adam Smith 006 (NeurIPS, 2024)

Oracle-Efficient Differentially Private Learning with Public Data. - Adam Block; Mark Bun; Rathin Desai; Abhishek Shetty; Zhiwei Steven Wu (NeurIPS, 2024)

Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections. - Mark Bun; Marco Gaboardi; Marcel Neunhoeffer; Wanrong Zhang 001 (Proc. ACM Manag. Data, 2024)

Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release. - Mark Bun; Marco Carmosino; Palak Jain 004; Gabriel Kaptchuk; Satchit Sivakumar (CoRR, 2025)