Jonathan Ullman

Research Papers

Each list is in reverse chronological order.
Authors are ordered alphabetically unless otherwise noted.
Papers are tagged with Paper Code Media Misc when available

Manuscripts
- Fair and Optimal Cohort Selection for Linear Utility arXiv
  Konstantina Bairaktari, Huy Le Nguyen, and Jonathan Ullman
Conference Publications
- Covariance-Aware Private Mean Estimation Without Private Covariance Estimation arXiv
  Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou
  Conference on Neural and Information Processing Systems (NeurIPS'21)
  Selected as a Spotlight Presentation
- Leveraging Public Data for Practical Private Query Release arXiv
  Terrance Liu, Thomas Steinke, Jonathan Ullman, Giuseppi Vietri, and Zhiwei Steven Wu
  International Conference on Machine Learning (ICML '21)
- The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation arXiv
  Albert Cheu and Jonathan Ullman
  ACM Symposium on Theory of Computing (STOC '21)
- Manipulation Attacks in Local Differential Privacy arXiv 1m Video
  Albert Cheu, Adam Smith, and Jonathan Ullman
  IEEE Symposium on Security and Privacy (IEEE S&P'21)
- Auditing Differentially Private Machine Learning: How Private is Private SGD? arXiv GitHub 15m Video
  Matthew Jagielski, Jonathan Ullman, and Alina Oprea (contribution order)
  Conference on Neural and Information Processing Systems (NeurIPS'20)
- CoinPress: Practical Private Mean and Covariance Estimation arXiv GitHub
  Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman
  Conference on Neural and Information Processing Systems (NeurIPS'20)
- Private Identity Testing for High-Dimensional Distributions arXiv
  Clément Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou
  Conference on Neural and Information Processing Systems (NeurIPS'20)
  Selected as a Spotlight Presentation
- Private Query Release Assisted by Public Data arXiv 15m Video
  Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and Zhiwei Steven Wu
  International Conference on Machine Learning (ICML'20)
- Private Mean Estimation of Heavy-Tailed Distributions arXiv
  Gautam Kamath, Vikrant Singhal, and Jonathan Ullman
  Conference on Learning Theory (COLT'20)
- The Power of Factorization Mechanisms in Local and Central Differential Privacy arXiv
  Alexander Edmonds, Aleksandar Nikolov, and Jonathan Ullman
  ACM Symposium on Theory of Computing (STOC'20)
- Efficient Private Algorithms for Learning Halfspaces arXiv
  Huy Lê Nguyễn, Jonathan Ullman, and Lydia Zakynthinou
  Conference on Algorithmic Learning Theory (ALT'20)
- Differentially Private Algorithms for Learning Mixtures of Gaussians arXiv
  Gautam Kamath, Or Sheffet, Vikrant Singhal, and Jonathan Ullman
  Conference on Neural and Information Processing Systems (NeurIPS'19)
- Efficiently Estimating Erdős-Rényi Graphs with Differential Privacy arXiv Poster
  Adam Sealfon and Jonathan Ullman
  Conference on Neural and Information Processing Systems (NeurIPS'19)
- Securely Sampling Biased Coins with Applications to Differential Privacy ePrint
  Jeffrey Champion, abhi shelat, and Jonathan Ullman
  ACM Conference on Computer Security (CCS'19)
- Differentially Private Fair Learning arXiv
  Matthew Jagielski, Michael Kearns, Jieming Mao, Alina Oprea, Aaron Roth, Saeed Sharifi-Malvajerdi, and Jonathan Ullman
  International Conference on Machine Learning (ICML'19)
- Privately Learning High-Dimensional Distributions arXiv Talk Video
  Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman
  Conference on Learning Theory (COLT'19)
- The Structure of Optimal Private Tests for Simple Hypotheses arXiv Talk Video
  Clément Canonne, Gautam Kamath, Audra McMillan, Adam Smith, and Jonathan Ullman
  ACM Symposium on Theory of Computing (STOC'19)
- Distributed Differential Privacy via Shuffling arXiv
  Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev
  IACR International Conference on Theory and Application of Cryptographic Techniques (EUROCRYPT'19)
- Local Differential Privacy for Evolving Data arXiv
  Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner
  Conference on Neural and Information Processing Systems (NeurIPS'18)
  Selected as a Spotlight Presentation
- The Limits of Post-Selection Generalization arXiv
  Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman
  Conference on Neural and Information Processing Systems (NeurIPS'18)
- Hardness of Non-Interactive Differential Privacy from One-Way Functions ePrint
  Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, and Daniel Wichs
  IACR International Cryptology Conference (CRYPTO'18)
- Skyline Identification in Multi-Armed Bandits arXiv
  Albert Cheu, Ravi Sundaram, and Jonathan Ullman
  IEEE International Symposium on Information Theory (ISIT'18)
- Tight Bounds for Differentially Private Selection arXiv
  Thomas Steinke and Jonathan Ullman
  IEEE Symposium on Foundations of Computer Science (FOCS'17)
- Fractional Set Cover in the Streaming Model arXiv
  Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, and Anak Yodpinyanee
  International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'17)
- The Price of Selection in Differential Privacy arXiv
  Mitali Bafna and Jonathan Ullman
  Conference on Computational Learning Theory (COLT'17)
- Multidimensional Dynamic Pricing for Welfare Maximization arXiv
  Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, and Zhiwei Steven Wu
  ACM Conference on Economics and Computation (EC'17)
  Invited to a special issue of Transactions on Economics and Computation for EC'17
- Make Up Your Mind: The Price of Online Queries in Differential Privacy arXiv
  Mark Bun, Thomas Steinke, Jonathan Ullman
  ACM-SIAM Symposium on Discrete Algorithms (SODA'17)
- Privacy Odometers and Filters: Pay-as-you-go Composition arXiv
  Ryan Rogers, Aaron Roth, Jonathan Ullman, and Salil Vadhan
  Conference on Neural and Information Processing Systems (NeurIPS'16)
- Strong Hardness of Privacy from Weak Traitor Tracing arXiv
  Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, and Mark Zhandry
  IACR Theory of Cryptography Conference (TCC'16B)
- Space Lower Bounds for Itemset Frequency Sketches arXiv
  Edo Liberty, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman
  ACM Symposium on Principles of Database Systems (PODS'16)
- Algorithmic Stability for Adaptive Data Analysis arXiv
  Raef Bassily, Kobbi Nissim, Uri Stemmer, Adam Smith, Thomas Steinke, and Jonathan Ullman
  ACM Symposium on Theory of Computing (STOC'16)
  Invited to a special issue of SIAM Journal on Computing for STOC'16
- Watch and Learn: Optimizing from Revealed Preferences Feedback arXiv SIGEcom Exchanges
  Aaron Roth, Jonathan Ullman, and Zhiwei Steven Wu
  ACM Symposium on Theory of Computing (STOC'16)
- When Can Limited Randomness Be Used in Repeated Games? arXiv
  Pavel Hubác̆ek, Moni Naor, Jonathan Ullman
  International Symposium on Algorithmic Game Theory (SAGT'15)
  Invited to a special issue of Theory of Computing for SAGT'15
- Robust Traceability from Trace Amounts PDF
  Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, and Salil Vadhan
  IEEE Symposium on Foundations of Computer Science (FOCS'15)
- Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery arXiv
  Thomas Steinke and Jonathan Ullman
  Conference on Computational Learning Theory (COLT'15)
- Inducing Approximately Optimal Flow Using Truthful Mediators arXiv
  Ryan Rogers, Aaron Roth, Jonathan Ullman, Zhiwei Steven Wu
  ACM Conference on Economics and Computation (EC'15)
- Private Multiplicative Weights Beyond Linear Queries arXiv
  Jonathan Ullman
  ACM Symposium on Principles of Database Systems (PODS'15)
- Preventing False Discovery in Interactive Data Analysis is Hard arXiv
  Moritz Hardt and Jonathan Ullman
  IEEE Symposium on Foundations of Computer Science (FOCS'14)
- Privately Solving Linear Programs arXiv
  Justin Hsu, Aaron Roth, Tim Roughgarden, Jonathan Ullman
  International Colloquium on Automata, Languages, and Programming Track A (ICALP'14)
- Fingerprinting Codes and the Price of Approximate Differential Privacy arXiv
  Mark Bun, Jonathan Ullman, and Salil Vadhan
  ACM Symposium on Theory of Computing (STOC'14)
  Invited to a special issue of SIAM Journal of Computing for STOC'14
- Faster Private Release of Marginals on Small Databases arXiv
  Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, and Andrew Wan
  Innovations in Theoretical Computer Science (ITCS'14)
- Robust Mediators in Large Games arXiv
  Michael Kearns, Mallesh Pai, Ryan Rogers, Aaron Roth, and Jonathan Ullman
  Innovations in Theoretical Computer Science (ITCS'14)
- Differential Privacy for the Analyst via Private Equilibrium Computation arXiv
  Justin Hsu, Aaron Roth, and Jonathan Ullman
  ACM Symposium on Thoery of Computing (STOC'13)
- Answering n^2+o(1) Counting Queries with Differential Privacy is Hard arXiv
  Jonathan Ullman
  ACM Symposium on Thoery of Computing (STOC'13)
  Invited to a special issue of SIAM Journal of Computing for STOC'13
- Faster Algorithms for Privately Releasing Marginals arXiv
  Justin Thaler, Jonathan Ullman, and Salil Vadhan
  International Colloquium on Automata, Languages, and Programming Track A (ICALP'12)
- Iterative Constructions and Private Data Release arXiv
  Anupam Gupta, Aaron Roth, and Jonathan Ullman
  IACR Theory of Cryptography Conference (TCC'12)
- Privately Releasing Conjunctions and the Statistical Query Barrier arXiv
  Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman
  ACM Symposium on Theory of Computing (STOC'12)
- PCPs and the Hardness of Generating Private Synthetic Data ECCC
  Jonathan Ullman and Salil Vadhan IACR Theory of Cryptography Conference (TCC'11)
  Invited to the Journal of Cryptology
- Course Allocation by Proxy Auction
  Scott Kominers, Mike Ruberry, Jonathan Ullman
  Workshop on Internet and Network Economics (WINE'10)
- The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows
  Shiva Kasiviswanathan, Mark Rudelson, Adam Smith, Jonathan Ullman
  ACM Symposium on Theory of Computing (STOC'10)
Journal Publications
- Manipulation Attacks in Local Differential Privacy arXiv 1m Video
  Albert Cheu, Adam Smith, and Jonathan Ullman
  Journal of Privacy and Confidentiality, 2021
- Efficiently Estimating Erdős-Rényi Graphs with Differential Privacy arXiv Poster
  Adam Sealfon and Jonathan Ullman
  Journal of Privacy and Confidentiality, 2021
- PCPs and the Hardness of Generating Private Synthetic Data ECCC
  Jonathan Ullman and Salil Vadhan Journal of Cryptology, 2020
Surveys and Other Writings

DifferentialPrivacy.org Website
Blog

A Primer on Private Statistics Blog Post PDF
Gautam Kamath and Jonathan Ullman

Subgaussian Concentration via Stability Arguments arXiv
Thomas Steinke and Jonathan Ullman

Technical Perspective: Building a Safety Net for Data Reuse CACM
Jonathan Ullman
Communications of the ACM, 2017

Exposed! A Survey of Attacks on Private Data ARSIA
Cynthia Dwork, Adam Smith, Thomas Steinke, and Jonathan Ullman
Annual Review of Statistics and its Applications

Updates

I am on sabbatical in Palo Alto for the 2021-22 academic year!

Contact

Research

Advising

Teaching

Service

Students and Advising

Current

Former

Service

Organizer

Program Committee / Track Chair

Program Committee Member

Reviewer

Teaching

Past Courses

Other

Research Papers

Manuscripts

Conference Publications

Journal Publications

Surveys and Other Writings