default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMark Bun
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
Journal Articles
- 2024
[j16]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): 94 (2024)- 2022
- [j15]Mark Bun, Justin Thaler:
Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci. 15(3-4): 229-423 (2022) - [j14]Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran:
Private and Online Learnability Are Equivalent. J. ACM 69(4): 28:1-28:34 (2022) - 2021
- [j13]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum 5: 543 (2021) - [j12]Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu:
Private Hypothesis Selection. IEEE Trans. Inf. Theory 67(3): 1981-2000 (2021) - [j11]Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. Theory Comput. 17: 1-46 (2021) - [j10]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-rank Can Increase under Intersection. ACM Trans. Comput. Theory 13(4): 24:1-24:17 (2021) - 2020
- [j9]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. SIAM J. Comput. 49(4) (2020) - [j8]Mark Bun, Justin Thaler:
Guest Column: Approximate Degree in Classical and Quantum Computing. SIGACT News 51(4): 48-72 (2020) - [j7]Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. 16: 1-71 (2020) - 2019
- [j6]Mark Bun, Kobbi Nissim, Uri Stemmer:
Simultaneous Private Learning of Multiple Concepts. J. Mach. Learn. Res. 20: 94:1-94:34 (2019) - [j5]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) - [j4]Mark Bun, Jelani Nelson, Uri Stemmer:
Heavy Hitters and the Structure of Local Privacy. ACM Trans. Algorithms 15(4): 51:1-51:40 (2019) - 2018
- [j3]Mark Bun, Jonathan R. Ullman, Salil P. Vadhan:
Fingerprinting Codes and the Price of Approximate Differential Privacy. SIAM J. Comput. 47(5): 1888-1938 (2018) - 2016
- [j2]Mark Bun, Justin Thaler:
Dual Polynomials for Collision and Element Distinctness. Theory Comput. 12(1): 1-34 (2016) - 2015
- [j1]Mark Bun, Justin Thaler:
Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput. 243: 2-25 (2015)
Conference and Workshop Papers
- 2024
- [c38]Mark Bun, Aloni Cohen, Rathin Desai:
Private PAC Learning May be Harder than Online Learning. ALT 2024: 362-389 - [c37]Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal:
Not All Learnable Distribution Classes are Privately Learnable. ALT 2024: 390-401 - 2023
- [c36]Maryam Aliakbarpour, Mark Bun, Adam Smith:
Hypothesis Selection with Memory Constraints. NeurIPS 2023 - [c35]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: 520-527 - [c34]Mark Bun, Nadezhda Voronova:
Approximate Degree Lower Bounds for Oracle Identification Problems. TQC 2023: 1:1-1:24 - 2022
- [c33]Gavin Brown, Mark Bun, Adam D. Smith:
Strong Memory Lower Bounds for Learning Natural Models. COLT 2022: 4989-5029 - [c32]Mark Bun, Marco Gaboardi, Ludmila Glinskih:
The Complexity of Verifying Boolean Programs as Differentially Private. CSF 2022: 396-411 - [c31]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: 1:1-1:24 - 2021
- [c30]Mark Bun, Marek Eliás, Janardhan Kulkarni:
Differentially Private Correlation Clustering. ICML 2021: 1136-1146 - [c29]Satchit Sivakumar, Mark Bun, Marco Gaboardi:
Multiclass versus Binary Differentially Private PAC Learning. NeurIPS 2021: 22943-22954 - [c28]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: 123-132 - 2020
- [c27]Mark Bun, Marco Leandro Carmosino, Jessica Sorrell:
Efficient, Noise-Tolerant, and Private Learning via Boosting. COLT 2020: 1031-1077 - [c26]Mark Bun, Roi Livni, Shay Moran:
An Equivalence Between Private Classification and Online Prediction. FOCS 2020: 389-402 - [c25]Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu:
New Oracle-Efficient Algorithms for Private Synthetic Data Release. ICML 2020: 9765-9774 - [c24]Mark Bun:
A Computational Separation between Private Learning and Online Learning. NeurIPS 2020 - 2019
- [c23]Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. APPROX-RANDOM 2019: 55:1-55:16 - [c22]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. ICALP 2019: 30:1-30:14 - [c21]Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu:
Private Hypothesis Selection. NeurIPS 2019: 156-167 - [c20]Mark Bun, Thomas Steinke:
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. NeurIPS 2019: 181-191 - [c19]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA 2019: 662-678 - [c18]Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke:
Towards Instance-Optimal Private Query Release. SODA 2019: 2480-2497 - 2018
- [c17]Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. APPROX-RANDOM 2018: 35:1-35:18 - [c16]Mark Bun, Jelani Nelson, Uri Stemmer:
Heavy Hitters and the Structure of Local Privacy. PODS 2018: 435-447 - [c15]Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke:
Composable and versatile privacy via truncated CDP. STOC 2018: 74-86 - [c14]Mark Bun, Robin Kothari, Justin Thaler:
The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC 2018: 297-310 - 2017
- [c13]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. FOCS 2017: 1-12 - [c12]Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi:
Differentially Private Submodular Maximization: Data Summarization in Disguise. ICML 2017: 2478-2487 - [c11]Mark Bun, Thomas Steinke, Jonathan R. Ullman:
Make Up Your Mind: The Price of Online Queries in Differential Privacy. SODA 2017: 1306-1325 - 2016
- [c10]Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC^0. ICALP 2016: 37:1-37:14 - [c9]Mark Bun, Kobbi Nissim, Uri Stemmer:
Simultaneous Private Learning of Multiple Concepts. ITCS 2016: 369-380 - [c8]Mark Bun, Mark Zhandry:
Order-Revealing Encryption and the Hardness of Private Learning. TCC (A1) 2016: 176-206 - [c7]Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan:
Separating Computational and Statistical Differential Privacy in the Client-Server Model. TCC (B1) 2016: 607-634 - [c6]Mark Bun, Thomas Steinke:
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. TCC (B1) 2016: 635-658 - 2015
- [c5]Mark Bun, Thomas Steinke:
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. APPROX-RANDOM 2015: 625-644 - [c4]Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan:
Differentially Private Release and Learning of Threshold Functions. FOCS 2015: 634-649 - [c3]Mark Bun, Justin Thaler:
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. ICALP (1) 2015: 268-280 - 2014
- [c2]Mark Bun, Jonathan R. Ullman, Salil P. Vadhan:
Fingerprinting codes and the price of approximate differential privacy. STOC 2014: 1-10 - 2013
- [c1]Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. ICALP (1) 2013: 303-314
Informal and Other Publications
- 2024
- [i50]Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal:
Not All Learnable Distribution Classes are Privately Learnable. CoRR abs/2402.00267 (2024) - [i49]Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, Steven Wu:
Oracle-Efficient Differentially Private Learning with Public Data. CoRR abs/2402.09483 (2024) - [i48]Mark Bun, Aloni Cohen, Rathin Desai:
Private PAC Learning May be Harder than Online Learning. CoRR abs/2402.11119 (2024) - 2023
- [i47]Shurong Lin, Mark Bun, Marco Gaboardi, Eric D. Kolaczyk, Adam Smith:
Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling. CoRR abs/2301.08324 (2023) - [i46]Mark Bun, Nadezhda Voronova:
Approximate degree lower bounds for oracle identification problems. CoRR abs/2303.03921 (2023) - [i45]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 abs/2303.12921 (2023) - [i44]Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, Wanrong Zhang:
Continual Release of Differentially Private Synthetic Data. CoRR abs/2306.07884 (2023) - [i43]Mark Bun, Marco Gaboardi, Ludmila Glinskih:
The Complexity of Verifying Boolean Programs as Differentially Private. CoRR abs/2309.04642 (2023) - [i42]Mark Bun, Nadezhda Voronova:
Approximate degree lower bounds for oracle identification problems. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [i41]Gavin Brown, Mark Bun, Adam D. Smith:
Strong Memory Lower Bounds for Learning Natural Models. CoRR abs/2206.04743 (2022) - 2021
- [i40]Mark Bun, Marek Eliás, Janardhan Kulkarni:
Differentially Private Correlation Clustering. CoRR abs/2102.08885 (2021) - [i39]Mark Bun, Marco Gaboardi, Satchit Sivakumar:
Multiclass versus Binary Differentially Private PAC Learning. CoRR abs/2107.10870 (2021) - 2020
- [i38]Mark Bun, Marco Leandro Carmosino, Jessica Sorrell:
Efficient, Noise-Tolerant, and Private Learning via Boosting. CoRR abs/2002.01100 (2020) - [i37]Mark Bun, Roi Livni, Shay Moran:
An Equivalence Between Private Classification and Online Prediction. CoRR abs/2003.00563 (2020) - [i36]Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu:
New Oracle-Efficient Algorithms for Private Synthetic Data Release. CoRR abs/2007.05453 (2020) - [i35]Mark Bun:
A Computational Separation between Private Learning and Online Learning. CoRR abs/2007.05665 (2020) - [i34]Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan:
Controlling Privacy Loss in Survey Sampling (Working Paper). CoRR abs/2007.12674 (2020) - [i33]Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar:
When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? CoRR abs/2012.06421 (2020) - 2019
- [i32]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. CoRR abs/1903.00544 (2019) - [i31]Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu:
Private Hypothesis Selection. CoRR abs/1905.13229 (2019) - [i30]Mark Bun, Thomas Steinke:
Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. CoRR abs/1906.02830 (2019) - [i29]Mark Bun, Nikhil S. Mande, Justin Thaler:
Sign-Rank Can Increase Under Intersection. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [i28]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR abs/1809.02254 (2018) - [i27]Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke:
Towards Instance-Optimal Private Query Release. CoRR abs/1811.03763 (2018) - [i26]Mark Bun, Robin Kothari, Justin Thaler:
Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. TR18 (2018) - [i25]Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [i24]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. CoRR abs/1703.05784 (2017) - [i23]Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR abs/1710.09079 (2017) - [i22]Mark Bun, Jelani Nelson, Uri Stemmer:
Heavy Hitters and the Structure of Local Privacy. CoRR abs/1711.04740 (2017) - [i21]Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. TR17 (2017) - [i20]Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [i19]Mark Bun, Thomas Steinke, Jonathan R. Ullman:
Make Up Your Mind: The Price of Online Queries in Differential Privacy. CoRR abs/1604.04618 (2016) - [i18]Mark Bun, Thomas Steinke:
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. CoRR abs/1605.02065 (2016) - [i17]Mark Bun, Justin Thaler:
Improved Bounds on the Sign-Rank of AC0. Electron. Colloquium Comput. Complex. TR16 (2016) - [i16]Mark Bun, Justin Thaler:
Approximate Degree and the Complexity of Depth Three Circuits. Electron. Colloquium Comput. Complex. TR16 (2016) - [i15]Mark Bun, Thomas Steinke:
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. IACR Cryptol. ePrint Arch. 2016: 816 (2016) - [i14]Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan:
Separating Computational and Statistical Differential Privacy in the Client-Server Model. IACR Cryptol. ePrint Arch. 2016: 820 (2016) - 2015
- [i13]Mark Bun, Justin Thaler:
Dual Polynomials for Collision and Element Distinctness. CoRR abs/1503.07261 (2015) - [i12]Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan:
Differentially Private Release and Learning of Threshold Functions. CoRR abs/1504.07553 (2015) - [i11]Mark Bun, Mark Zhandry:
Order-Revealing Encryption and the Hardness of Private Learning. CoRR abs/1505.00388 (2015) - [i10]Mark Bun, Kobbi Nissim, Uri Stemmer:
Simultaneous Private Learning of Multiple Concepts. CoRR abs/1511.08552 (2015) - [i9]Mark Bun, Justin Thaler:
Dual Polynomials for Collision and Element Distinctness. Electron. Colloquium Comput. Complex. TR15 (2015) - [i8]Mark Bun, Mark Zhandry:
Order-Revealing Encryption and the Hardness of Private Learning. IACR Cryptol. ePrint Arch. 2015: 417 (2015) - 2014
- [i7]Mark Bun, Thomas Steinke:
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. CoRR abs/1412.2457 (2014) - [i6]Mark Bun, Thomas Steinke:
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [i5]Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. CoRR abs/1302.6191 (2013) - [i4]Mark Bun, Justin Thaler:
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. CoRR abs/1311.1616 (2013) - [i3]Mark Bun, Jonathan R. Ullman, Salil P. Vadhan:
Fingerprinting Codes and the Price of Approximate Differential Privacy. CoRR abs/1311.3158 (2013) - [i2]Mark Bun, Justin Thaler:
Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. Electron. Colloquium Comput. Complex. TR13 (2013) - [i1]Mark Bun, Justin Thaler:
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. Electron. Colloquium Comput. Complex. TR13 (2013)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-10-07 22:22 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
