Mark Bun - RankMe

114 papers A* 26A 3B 2Journal 72Unranked 10

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Interactive Proofs for Distribution Testing with Conditional Oracles. ITCS Ari Biswas, Mark Bun, Clément L. Canonne, Satchit Sivakumar
2026	J	`jnl`	Privately Learning Decision Lists and a Differentially Private Winnow. CoRR Mark Bun, William Fang
2026	J	`jnl`	Separating Oblivious and Adaptive Differential Privacy under Continual Observation. CoRR Mark Bun, Marco Gaboardi, Connor Wagaman
2025	—	`ed.`	6th Symposium on Foundations of Responsible Computing, FORC 2025, Stanford University, CA, USA, June 4-6, 2025 FORC Mark Bun
2025	J	`jnl`	Differentially Private Wasserstein Barycenters. CoRR Anming Gu, Sasidhar Kunapuli, Mark Bun, Edward Chien, Kristjan Greenewald
2025	J	`jnl`	Enforcing Demographic Coherence: A Harms Aware Framework for Reasoning about Private Data Release. CoRR Mark Bun, Marco Carmosino, Palak Jain, Gabriel Kaptchuk, Satchit Sivakumar
2025	J	`jnl`	Interactive Proofs For Distribution Testing With Conditional Oracles. CoRR Ari Biswas, Mark Bun, Clément Canonne, Satchit Sivakumar
2025	J	`jnl`	Interactive Proofs For Distribution Testing With Conditional Oracles. Electron. Colloquium Comput. Complex. Ari Biswas, Mark Bun, Clément Canonne, Satchit Sivakumar
2024	J	`jnl`	Continual Release of Differentially Private Synthetic Data from Longitudinal Data Collections. Proc. ACM Manag. Data Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, Wanrong Zhang
2024	B	`conf`	Not All Learnable Distribution Classes are Privately Learnable. ALT Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
2024	J	`jnl`	Not All Learnable Distribution Classes are Privately Learnable. CoRR Mark Bun, Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
2024	A*	`conf`	Optimal Hypothesis Selection in (Almost) Linear Time. NeurIPS Maryam Aliakbarpour, Mark Bun, Adam Smith
2024	A*	`conf`	Oracle-Efficient Differentially Private Learning with Public Data. NeurIPS Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, Zhiwei Steven Wu
2024	J	`jnl`	Oracle-Efficient Differentially Private Learning with Public Data. CoRR Adam Block, Mark Bun, Rathin Desai, Abhishek Shetty, Zhiwei Steven Wu
2024	B	`conf`	Private PAC Learning May be Harder than Online Learning. ALT Mark Bun, Aloni Cohen, Rathin Desai
2024	J	`jnl`	Private PAC Learning May be Harder than Online Learning. CoRR Mark Bun, Aloni Cohen, Rathin Desai
2023	—	`conf`	Approximate Degree Lower Bounds for Oracle Identification Problems. TQC Mark Bun, Nadezhda Voronova
2023	J	`jnl`	Approximate degree lower bounds for oracle identification problems. CoRR Mark Bun, Nadezhda Voronova
2023	J	`jnl`	Approximate degree lower bounds for oracle identification problems. Electron. Colloquium Comput. Complex. Mark Bun, Nadezhda Voronova
2023	J	`jnl`	Continual Release of Differentially Private Synthetic Data. CoRR Mark Bun, Marco Gaboardi, Marcel Neunhoeffer, Wanrong Zhang
2023	J	`jnl`	Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling. CoRR Shurong Lin, Mark Bun, Marco Gaboardi, Eric D. Kolaczyk, Adam Smith
2023	A*	`conf`	Hypothesis Selection with Memory Constraints. NeurIPS Maryam Aliakbarpour, Mark Bun, Adam Smith
2023	A*	`conf`	Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. STOC Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell
2023	J	`jnl`	Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. CoRR Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell
2023	J	`jnl`	The Complexity of Verifying Boolean Programs as Differentially Private. CoRR Mark Bun, Marco Gaboardi, Ludmila Glinskih
2022	J	`jnl`	Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci. Mark Bun, Justin Thaler
2022	—	`conf`	Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling. FORC Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, Jayshree Sarathy
2022	J	`jnl`	Private and Online Learnability Are Equivalent. J. ACM Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, Shay Moran
2022	A*	`conf`	Strong Memory Lower Bounds for Learning Natural Models. COLT Gavin Brown, Mark Bun, Adam D. Smith
2022	J	`jnl`	Strong Memory Lower Bounds for Learning Natural Models. CoRR Gavin Brown, Mark Bun, Adam D. Smith
2022	A	`conf`	The Complexity of Verifying Boolean Programs as Differentially Private. CSF Mark Bun, Marco Gaboardi, Ludmila Glinskih
2021	A*	`conf`	Differentially Private Correlation Clustering. ICML Mark Bun, Marek Eliás, Janardhan Kulkarni
2021	J	`jnl`	Differentially Private Correlation Clustering. CoRR Mark Bun, Marek Eliás, Janardhan Kulkarni
2021	A*	`conf`	Multiclass versus Binary Differentially Private PAC Learning. NeurIPS Satchit Sivakumar, Mark Bun, Marco Gaboardi
2021	J	`jnl`	Multiclass versus Binary Differentially Private PAC Learning. CoRR Mark Bun, Marco Gaboardi, Satchit Sivakumar
2021	J	`jnl`	Private Hypothesis Selection. IEEE Trans. Inf. Theory Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu
2021	J	`jnl`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. Quantum Mark Bun, Robin Kothari, Justin Thaler
2021	J	`jnl`	Sign-rank Can Increase under Intersection. ACM Trans. Comput. Theory Mark Bun, Nikhil S. Mande, Justin Thaler
2021	J	`jnl`	The Large-Error Approximate Degree of AC Theory Comput. Mark Bun, Justin Thaler
2021	A*	`conf`	When is memorization of irrelevant training data necessary for high-accuracy learning? STOC Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar
2020	A*	`conf`	A Computational Separation between Private Learning and Online Learning. NeurIPS Mark Bun
2020	J	`jnl`	A Computational Separation between Private Learning and Online Learning. CoRR Mark Bun
2020	J	`jnl`	A Nearly Optimal Lower Bound on the Approximate Degree of AC SIAM J. Comput. Mark Bun, Justin Thaler
2020	A*	`conf`	An Equivalence Between Private Classification and Online Prediction. FOCS Mark Bun, Roi Livni, Shay Moran
2020	J	`jnl`	An Equivalence Between Private Classification and Online Prediction. CoRR Mark Bun, Roi Livni, Shay Moran
2020	J	`jnl`	Controlling Privacy Loss in Survey Sampling (Working Paper). CoRR Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan
2020	A*	`conf`	Efficient, Noise-Tolerant, and Private Learning via Boosting. COLT Mark Bun, Marco Leandro Carmosino, Jessica Sorrell
2020	J	`jnl`	Efficient, Noise-Tolerant, and Private Learning via Boosting. CoRR Mark Bun, Marco Leandro Carmosino, Jessica Sorrell
2020	J	`jnl`	Guest Column: Approximate Degree in Classical and Quantum Computing. SIGACT News Mark Bun, Justin Thaler
2020	A*	`conf`	New Oracle-Efficient Algorithms for Private Synthetic Data Release. ICML Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu
2020	J	`jnl`	New Oracle-Efficient Algorithms for Private Synthetic Data Release. CoRR Giuseppe Vietri, Grace Tian, Mark Bun, Thomas Steinke, Zhiwei Steven Wu
2020	J	`jnl`	The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Theory Comput. Mark Bun, Robin Kothari, Justin Thaler
2020	J	`jnl`	When is Memorization of Irrelevant Training Data Necessary for High-Accuracy Learning? CoRR Gavin Brown, Mark Bun, Vitaly Feldman, Adam D. Smith, Kunal Talwar
2019	A*	`conf`	Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. NeurIPS Mark Bun, Thomas Steinke
2019	J	`jnl`	Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. CoRR Mark Bun, Thomas Steinke
2019	J	`jnl`	Heavy Hitters and the Structure of Local Privacy. ACM Trans. Algorithms Mark Bun, Jelani Nelson, Uri Stemmer
2019	J	`jnl`	Make Up Your Mind: The Price of Online Queries in Differential Privacy. J. Priv. Confidentiality Mark Bun, Thomas Steinke, Jonathan R. Ullman
2019	A*	`conf`	Private Hypothesis Selection. NeurIPS Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu
2019	J	`jnl`	Private Hypothesis Selection. CoRR Mark Bun, Gautam Kamath, Thomas Steinke, Zhiwei Steven Wu
2019	A*	`conf`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. SODA Mark Bun, Robin Kothari, Justin Thaler
2019	A*	`conf`	Sign-Rank Can Increase Under Intersection. ICALP Mark Bun, Nikhil S. Mande, Justin Thaler
2019	J	`jnl`	Sign-Rank Can Increase Under Intersection. CoRR Mark Bun, Nikhil S. Mande, Justin Thaler
2019	J	`jnl`	Sign-Rank Can Increase Under Intersection. Electron. Colloquium Comput. Complex. Mark Bun, Nikhil S. Mande, Justin Thaler
2019	J	`jnl`	Simultaneous Private Learning of Multiple Concepts. J. Mach. Learn. Res. Mark Bun, Kobbi Nissim, Uri Stemmer
2019	—	`conf`	The Large-Error Approximate Degree of AC APPROX-RANDOM Mark Bun, Justin Thaler
2019	A*	`conf`	Towards Instance-Optimal Private Query Release. SODA Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke
2018	—	`conf`	Approximate Degree and the Complexity of Depth Three Circuits. APPROX-RANDOM Mark Bun, Justin Thaler
2018	A*	`conf`	Composable and versatile privacy via truncated CDP. STOC Mark Bun, Cynthia Dwork, Guy N. Rothblum, Thomas Steinke
2018	J	`jnl`	Fingerprinting Codes and the Price of Approximate Differential Privacy. SIAM J. Comput. Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
2018	A*	`conf`	Heavy Hitters and the Structure of Local Privacy. PODS Mark Bun, Jelani Nelson, Uri Stemmer
2018	J	`jnl`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. CoRR Mark Bun, Robin Kothari, Justin Thaler
2018	J	`jnl`	Quantum algorithms and approximating polynomials for composed functions with shared inputs. Electron. Colloquium Comput. Complex. Mark Bun, Robin Kothari, Justin Thaler
2018	J	`jnl`	The Large-Error Approximate Degree of AC Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler
2018	A*	`conf`	The polynomial method strikes back: tight quantum query bounds via dual polynomials. STOC Mark Bun, Robin Kothari, Justin Thaler
2018	J	`jnl`	Towards Instance-Optimal Private Query Release. CoRR Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, Thomas Steinke
2017	A*	`conf`	A Nearly Optimal Lower Bound on the Approximate Degree of AC FOCS Mark Bun, Justin Thaler
2017	J	`jnl`	A Nearly Optimal Lower Bound on the Approximate Degree of AC CoRR Mark Bun, Justin Thaler
2017	J	`jnl`	A Nearly Optimal Lower Bound on the Approximate Degree of AC Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler
2017	A*	`conf`	Differentially Private Submodular Maximization: Data Summarization in Disguise. ICML Marko Mitrovic, Mark Bun, Andreas Krause, Amin Karbasi
2017	J	`jnl`	Heavy Hitters and the Structure of Local Privacy. CoRR Mark Bun, Jelani Nelson, Uri Stemmer
2017	A*	`conf`	Make Up Your Mind: The Price of Online Queries in Differential Privacy. SODA Mark Bun, Thomas Steinke, Jonathan R. Ullman
2017	J	`jnl`	The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. CoRR Mark Bun, Robin Kothari, Justin Thaler
2017	J	`jnl`	The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. Electron. Colloquium Comput. Complex. Mark Bun, Robin Kothari, Justin Thaler
2016	J	`jnl`	Approximate Degree and the Complexity of Depth Three Circuits. Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler
2016	—	`conf`	Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. TCC (B1) Mark Bun, Thomas Steinke
2016	J	`jnl`	Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. CoRR Mark Bun, Thomas Steinke
2016	J	`jnl`	Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds. IACR Cryptol. ePrint Arch. Mark Bun, Thomas Steinke
2016	J	`jnl`	Dual Polynomials for Collision and Element Distinctness. Theory Comput. Mark Bun, Justin Thaler
2016	J	`jnl`	Improved Bounds on the Sign-Rank of AC Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler
2016	A*	`conf`	Improved Bounds on the Sign-Rank of AC^0. ICALP Mark Bun, Justin Thaler
2016	J	`jnl`	Make Up Your Mind: The Price of Online Queries in Differential Privacy. CoRR Mark Bun, Thomas Steinke, Jonathan R. Ullman
2016	—	`conf`	Order-Revealing Encryption and the Hardness of Private Learning. TCC (A1) Mark Bun, Mark Zhandry
2016	—	`conf`	Separating Computational and Statistical Differential Privacy in the Client-Server Model. TCC (B1) Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan
2016	J	`jnl`	Separating Computational and Statistical Differential Privacy in the Client-Server Model. IACR Cryptol. ePrint Arch. Mark Bun, Yi-Hsiu Chen, Salil P. Vadhan
2016	A	`conf`	Simultaneous Private Learning of Multiple Concepts. ITCS Mark Bun, Kobbi Nissim, Uri Stemmer
2015	A*	`conf`	Differentially Private Release and Learning of Threshold Functions. FOCS Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan
2015	J	`jnl`	Differentially Private Release and Learning of Threshold Functions. CoRR Mark Bun, Kobbi Nissim, Uri Stemmer, Salil P. Vadhan
2015	J	`jnl`	Dual Polynomials for Collision and Element Distinctness. CoRR Mark Bun, Justin Thaler
2015	J	`jnl`	Dual Polynomials for Collision and Element Distinctness. Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler
2015	J	`jnl`	Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput. Mark Bun, Justin Thaler
2015	—	`conf`	Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. ICALP (1) Mark Bun, Justin Thaler
2015	J	`jnl`	Order-Revealing Encryption and the Hardness of Private Learning. CoRR Mark Bun, Mark Zhandry
2015	J	`jnl`	Order-Revealing Encryption and the Hardness of Private Learning. IACR Cryptol. ePrint Arch. Mark Bun, Mark Zhandry
2015	J	`jnl`	Simultaneous Private Learning of Multiple Concepts. CoRR Mark Bun, Kobbi Nissim, Uri Stemmer
2015	—	`conf`	Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. APPROX-RANDOM Mark Bun, Thomas Steinke
2014	A*	`conf`	Fingerprinting codes and the price of approximate differential privacy. STOC Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
2014	J	`jnl`	Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. CoRR Mark Bun, Thomas Steinke
2014	J	`jnl`	Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. Electron. Colloquium Comput. Complex. Mark Bun, Thomas Steinke
2013	J	`jnl`	Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities CoRR Mark Bun, Justin Thaler
2013	—	`conf`	Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. ICALP (1) Mark Bun, Justin Thaler
2013	J	`jnl`	Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities. Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler
2013	J	`jnl`	Fingerprinting Codes and the Price of Approximate Differential Privacy. CoRR Mark Bun, Jonathan R. Ullman, Salil P. Vadhan
2013	J	`jnl`	Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. CoRR Mark Bun, Justin Thaler
2013	J	`jnl`	Hardness Amplification and the Approximate Degree of Constant-Depth Circuits. Electron. Colloquium Comput. Complex. Mark Bun, Justin Thaler