Mark Bun

ORCID

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 85

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

STOC

NeurIPS

Publications

Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
Not All Learnable Distribution Classes are Privately Learnable. ALT (2024)
Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
Not All Learnable Distribution Classes are Privately Learnable. CoRR (2024)
Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, Wanrong Zhang
Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections. Proc. ACM Manag. Data 2 (2) (2024)
Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, Steven Wu
Oracle-Efficient Differentially Private Learning with Public Data. CoRR (2024)
Mark Bun, Aloni Cohen, Rathin Desai
Private PAC Learning May be Harder than Online Learning. CoRR (2024)
Mark Bun, Aloni Cohen, Rathin Desai
Private PAC Learning May be Harder than Online Learning. ALT (2024)
Mark Bun, Nadezhda Voronova
Approximate Degree Lower Bounds for Oracle Identification Problems. TQC (2023)
Shurong Lin, Mark Bun, Marco Gaboardi, Eric D. Kolaczyk, Adam Smith
Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling. CoRR (2023)
Maryam Aliakbarpour, Mark Bun, Adam Smith
Hypothesis Selection with Memory Constraints. NeurIPS (2023)
Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, Wanrong Zhang
Continual Release of Differentially Private Synthetic Data. CoRR (2023)
Mark Bun, Nadezhda Voronova
Approximate degree lower bounds for oracle identification problems. Electron. Colloquium Comput. Complex. (2023)
Mark Bun, Marco Gaboardi, Ludmila Glinskih
The Complexity of Verifying Boolean Programs as Differentially Private. CoRR (2023)
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. CoRR (2023)
Mark Bun, Nadezhda Voronova
Approximate degree lower bounds for oracle identification problems. CoRR (2023)
Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. STOC (2023)
Mark Bun, Marco Gaboardi, Ludmila Glinskih
The Complexity of Verifying Boolean Programs as Differentially Private. CSF (2022)
Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran
Private and Online Learnability Are Equivalent. J. ACM 69 (4) (2022)
Gavin Brown, Mark Bun, Adam D. Smith
Strong Memory Lower Bounds for Learning Natural Models. CoRR (2022)
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 (2022)
Gavin Brown, Mark Bun, Adam D. Smith
Strong Memory Lower Bounds for Learning Natural Models. COLT (2022)
Mark Bun, Justin Thaler
Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci. 15 (3-4) (2022)
Mark Bun, Justin Thaler
. Theory Comput. 17 (2021)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-rank Can Increase under Intersection. ACM Trans. Comput. Theory 13 (4) (2021)
Mark Bun, Marek Eliás, Janardhan Kulkarni
Differentially Private Correlation Clustering. CoRR (2021)
Satchit Sivakumar, Mark Bun, Marco Gaboardi
Multiclass versus Binary Differentially Private PAC Learning. NeurIPS (2021)
Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar
When is memorization of irrelevant training data necessary for high-accuracy learning? STOC (2021)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum 5 (2021)
Mark Bun, Marek Eliás, Janardhan Kulkarni
Differentially Private Correlation Clustering. ICML (2021)
Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu
Private Hypothesis Selection. IEEE Trans. Inf. Theory 67 (3) (2021)
Mark Bun, Marco Gaboardi, Satchit Sivakumar
Multiclass versus Binary Differentially Private PAC Learning. CoRR (2021)
Mark Bun, Marco Leandro Carmosino, Jessica Sorrell
Efficient, Noise-Tolerant, and Private Learning via Boosting. COLT (2020)
Mark Bun
A Computational Separation between Private Learning and Online Learning. CoRR (2020)
Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? CoRR (2020)
Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu
New Oracle-Efficient Algorithms for Private Synthetic Data Release. ICML (2020)
Mark Bun, Marco Leandro Carmosino, Jessica Sorrell
Efficient, Noise-Tolerant, and Private Learning via Boosting. CoRR (2020)
Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu
New Oracle-Efficient Algorithms for Private Synthetic Data Release. CoRR (2020)
Mark Bun, Justin Thaler
. SIAM J. Comput. 49 (4) (2020)
Mark Bun
A Computational Separation between Private Learning and Online Learning. NeurIPS (2020)
Mark Bun, Justin Thaler
Guest Column: Approximate Degree in Classical and Quantum Computing. SIGACT News 51 (4) (2020)
Mark Bun, Roi Livni, Shay Moran
An Equivalence Between Private Classification and Online Prediction. CoRR (2020)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. 16 (2020)
Mark Bun, Roi Livni, Shay Moran
An Equivalence Between Private Classification and Online Prediction. FOCS (2020)
Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan
Controlling Privacy Loss in Survey Sampling (Working Paper). CoRR (2020)
Mark Bun, Justin Thaler
. APPROX-RANDOM (2019)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-Rank Can Increase Under Intersection. CoRR (2019)
Mark Bun, Kobbi Nissim, Uri Stemmer
Simultaneous Private Learning of Multiple Concepts. J. Mach. Learn. Res. 20 (2019)
Mark Bun, Thomas Steinke, Jonathan R. Ullman
Make Up Your Mind: The Price of Online Queries in Differential Privacy. J. Priv. Confidentiality 9 (1) (2019)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA (2019)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-Rank Can Increase Under Intersection. Electron. Colloquium Comput. Complex. 26 (2019)
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke
Towards Instance-Optimal Private Query Release. SODA (2019)
Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu
Private Hypothesis Selection. NeurIPS (2019)
Mark Bun, Thomas Steinke
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. CoRR (2019)
Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu
Private Hypothesis Selection. CoRR (2019)
Mark Bun, Jelani Nelson, Uri Stemmer
Heavy Hitters and the Structure of Local Privacy. ACM Trans. Algorithms 15 (4) (2019)
Mark Bun, Thomas Steinke
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. NeurIPS (2019)
Mark Bun, Nikhil S. Mande, Justin Thaler
Sign-Rank Can Increase Under Intersection. ICALP (2019)
Mark Bun, Justin Thaler
Approximate Degree and the Complexity of Depth Three Circuits. APPROX-RANDOM (2018)
Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
Fingerprinting Codes and the Price of Approximate Differential Privacy. SIAM J. Comput. 47 (5) (2018)
Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke
Composable and versatile privacy via truncated CDP. STOC (2018)
Mark Bun, Jelani Nelson, Uri Stemmer
Heavy Hitters and the Structure of Local Privacy. PODS (2018)
Mark Bun, Robin Kothari, Justin Thaler
The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC (2018)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. 25 (2018)
Mark Bun, Robin Kothari, Justin Thaler
Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR (2018)
Mark Bun, Justin Thaler
. Electron. Colloquium Comput. Complex. 25 (2018)
Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke
Towards Instance-Optimal Private Query Release. CoRR (2018)
Mark Bun, Thomas Steinke, Jonathan R. Ullman
Make Up Your Mind: The Price of Online Queries in Differential Privacy. SODA (2017)
Mark Bun, Justin Thaler
. Electron. Colloquium Comput. Complex. 24 (2017)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR (2017)
Mark Bun, Robin Kothari, Justin Thaler
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. 24 (2017)
Mark Bun, Justin Thaler
. CoRR (2017)
Mark Bun, Justin Thaler
. FOCS (2017)
Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi
Differentially Private Submodular Maximization: Data Summarization in Disguise. ICML (2017)
Mark Bun, Jelani Nelson, Uri Stemmer
Heavy Hitters and the Structure of Local Privacy. CoRR (2017)
Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan
Separating Computational and Statistical Differential Privacy in the Client-Server Model. TCC (B1) (2016)
Mark Bun, Justin Thaler
. Electron. Colloquium Comput. Complex. 23 (2016)
Mark Bun, Justin Thaler
Approximate Degree and the Complexity of Depth Three Circuits. Electron. Colloquium Comput. Complex. 23 (2016)
Mark Bun, Justin Thaler
Improved Bounds on the Sign-Rank of AC^0. ICALP (2016)
Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan
Separating Computational and Statistical Differential Privacy in the Client-Server Model. IACR Cryptol. ePrint Arch. 2016 (2016)
Mark Bun, Mark Zhandry
Order-Revealing Encryption and the Hardness of Private Learning. TCC (A1) (2016)
Mark Bun, Thomas Steinke
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. CoRR (2016)
Mark Bun, Justin Thaler
Dual Polynomials for Collision and Element Distinctness. Theory Comput. 12 (1) (2016)
Mark Bun, Thomas Steinke, Jonathan R. Ullman
Make Up Your Mind: The Price of Online Queries in Differential Privacy. CoRR (2016)
Mark Bun, Thomas Steinke
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. TCC (B1) (2016)
Mark Bun, Thomas Steinke
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. IACR Cryptol. ePrint Arch. 2016 (2016)
Mark Bun, Kobbi Nissim, Uri Stemmer
Simultaneous Private Learning of Multiple Concepts. ITCS (2016)
Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan
Differentially Private Release and Learning of Threshold Functions. FOCS (2015)
Mark Bun, Justin Thaler
Dual Polynomials for Collision and Element Distinctness. Electron. Colloquium Comput. Complex. 22 (2015)
Mark Bun, Kobbi Nissim, Uri Stemmer
Simultaneous Private Learning of Multiple Concepts. CoRR (2015)
Mark Bun, Mark Zhandry
Order-Revealing Encryption and the Hardness of Private Learning. CoRR (2015)
Mark Bun, Thomas Steinke
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. APPROX-RANDOM (2015)
Mark Bun, Mark Zhandry
Order-Revealing Encryption and the Hardness of Private Learning. IACR Cryptol. ePrint Arch. 2015 (2015)
Mark Bun, Justin Thaler
Dual Polynomials for Collision and Element Distinctness. CoRR (2015)
Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan
Differentially Private Release and Learning of Threshold Functions. CoRR (2015)
Mark Bun, Justin Thaler
Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput. 243 (2015)
Mark Bun, Justin Thaler
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. ICALP (1) (2015)
Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
Fingerprinting codes and the price of approximate differential privacy. STOC (2014)
Mark Bun, Thomas Steinke
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. CoRR (2014)
Mark Bun, Thomas Steinke
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. Electron. Colloquium Comput. Complex. 21 (2014)
Mark Bun, Justin Thaler
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities CoRR (2013)
Mark Bun, Justin Thaler
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. Electron. Colloquium Comput. Complex. 20 (2013)

Mark Bun.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mark Bun