Mark Bun

Aloni Cohen

Rathin Desai

Proceedings of the International Conference on Algorithmic Learning Theory, 2024

Not All Learnable Distribution Classes are Privately Learnable.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Algorithmic Learning Theory, 2024

2023

Approximate degree lower bounds for oracle identification problems.

[BibT_eX]

[DOI]

Nadezhda Voronova

Electron. Colloquium Comput. Complex., 2023

Continual Release of Differentially Private Synthetic Data.

[BibT_eX]

[DOI]

CoRR, 2023

Differentially Private Confidence Intervals for Proportions under Stratified Random Sampling.

[BibT_eX]

[DOI]

CoRR, 2023

Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Hypothesis Selection with Memory Constraints.

[BibT_eX]

[DOI]

Maryam Aliakbarpour

Adam Smith

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

Private and Online Learnability Are Equivalent.

[BibT_eX]

[DOI]

J. ACM, 2022

Approximate Degree in Classical and Quantum Computing.

[BibT_eX]

[DOI]

Found. Trends Theor. Comput. Sci., 2022

Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling.

[BibT_eX]

[DOI]

Proceedings of the 3rd Symposium on Foundations of Responsible Computing, 2022

The Complexity of Verifying Boolean Programs as Differentially Private.

[BibT_eX]

[DOI]

Marco Gaboardi

Ludmila Glinskih

Proceedings of the 35th IEEE Computer Security Foundations Symposium, 2022

Strong Memory Lower Bounds for Learning Natural Models.

[BibT_eX]

[DOI]

Gavin Brown

Adam D. Smith

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Private Hypothesis Selection.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 2021

Quantum algorithms and approximating polynomials for composed functions with shared inputs.

[BibT_eX]

[DOI]

Robin Kothari

Quantum, 2021

When is memorization of irrelevant training data necessary for high-accuracy learning?

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Multiclass versus Binary Differentially Private PAC Learning.

[BibT_eX]

[DOI]

Satchit Sivakumar

Marco Gaboardi

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Differentially Private Correlation Clustering.

[BibT_eX]

[DOI]

Marek Eliás

Janardhan Kulkarni

Proceedings of the 38th International Conference on Machine Learning, 2021

2020

Guest Column: Approximate Degree in Classical and Quantum Computing.

[BibT_eX]

[DOI]

SIGACT News, 2020

A Nearly Optimal Lower Bound on the Approximate Degree of AC0.

[BibT_eX]

[DOI]

SIAM J. Comput., 2020

Controlling Privacy Loss in Survey Sampling (Working Paper).

[BibT_eX]

[DOI]

CoRR, 2020

A Computational Separation between Private Learning and Online Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

New Oracle-Efficient Algorithms for Private Synthetic Data Release.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

An Equivalence Between Private Classification and Online Prediction.

[BibT_eX]

[DOI]

Roi Livni

Shay Moran

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Efficient, Noise-Tolerant, and Private Learning via Boosting.

[BibT_eX]

[DOI]

Marco Leandro Carmosino

Jessica Sorrell

Proceedings of the Conference on Learning Theory, 2020

2019

Heavy Hitters and the Structure of Local Privacy.

[BibT_eX]

[DOI]

Jelani Nelson

Uri Stemmer

ACM Trans. Algorithms, 2019

Make Up Your Mind: The Price of Online Queries in Differential Privacy.

[BibT_eX]

[DOI]

Jonathan R. Ullman

J. Priv. Confidentiality, 2019

Simultaneous Private Learning of Multiple Concepts.

[BibT_eX]

[DOI]

Kobbi Nissim

Uri Stemmer

J. Mach. Learn. Res., 2019

Sign-Rank Can Increase Under Intersection.

[BibT_eX]

[DOI]

Nikhil S. Mande

Electron. Colloquium Comput. Complex., 2019

Towards Instance-Optimal Private Query Release.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

2018

Fingerprinting Codes and the Price of Approximate Differential Privacy.

[BibT_eX]

[DOI]

Jonathan R. Ullman

Salil P. Vadhan

SIAM J. Comput., 2018

The Large-Error Approximate Degree of AC0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Composable and versatile privacy via truncated CDP.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017

The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials.

[BibT_eX]

[DOI]

Robin Kothari

Electron. Colloquium Comput. Complex., 2017

Differentially Private Submodular Maximization: Data Summarization in Disguise.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

2016

Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2016

Separating Computational and Statistical Differential Privacy in the Client-Server Model.

[BibT_eX]

[DOI]

Yi-Hsiu Chen

Salil P. Vadhan

IACR Cryptol. ePrint Arch., 2016

Approximate Degree and the Complexity of Depth Three Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Improved Bounds on the Sign-Rank of AC0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Improved Bounds on the Sign-Rank of AC^0.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

Order-Revealing Encryption and the Hardness of Private Learning.

[BibT_eX]

[DOI]

Mark Zhandry

IACR Cryptol. ePrint Arch., 2015

Dual Polynomials for Collision and Element Distinctness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Differentially Private Release and Learning of Threshold Functions.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Hardness Amplification and the Approximate Degree of Constant-Depth Circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.

[BibT_eX]

[DOI]