Jonathan Ullman

Research Papers

I am committed to making all of my papers freely available as quickly as possible by hosting them on arXiv or similar open access preprint servers, and these preprints should be considered the authoritative version of the paper. When possible I will also link to any associated code, data, talks, or expository writing available. These resources are indicated with paper code talk misc tags.

I prefer not to order authors by contribution, but sometimes the norms of the community and the needs of students demand it. Author ordering is alphabetical except where otherwise noted.

Manuscripts

Multitask Learning via Shared Features: Algorithms and Hardness arXiv
Konstantina Bairaktari, Guy Blanc, Li-Yang Tan, Jonathan Ullman, and Lydia Zakynthinou

SNAP: Efficient Extraction of Private Properties with Poisoning arXiv
Harsh Chaudhuri, John Abascal, Alina Oprea, Matthew Jagielski, Florian Tramèr, and Jonathan Ullman (contribution order)

How to Combine Membership-Inference Attacks on Multiple Updated Models arXiv
Matthew Jagielski*, Stanley Wu*, Alina Oprea, Jonathan Ullman, and Roxana Geambasu (contribution order)

Fair and Optimal Cohort Selection for Linear Utility arXiv
Konstantina Bairaktari, Huy Le Nguyen, and Jonathan Ullman

Conference Publications

A Private and Computationally Efficient Estimator for Unbounded Gaussians arXiv
Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman
Conference on Learning Theory (COLT '22)

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 60m Video
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 60m Video
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

Multidimensional Dynamic Pricing for Welfare Maximization
Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, and Zhiwei Steven Wu
ACM Transactions on Economics and Computation, 2020

The Fienberg Problem: How to Allow Human Interactive Data Analysis in the Age of Differential Privacy
Cynthia Dwork and Jonathan Ullman
Journal of Privacy and Confidentiality, 2018. Special issue commemorating Steve Feinberg.

Fingerprinting Codes and the Price of Approximate Differential Privacy arXiv
Mark Bun, Jonathan Ullman, and Salil Vadhan
SIAM Journal on Computing, 2018
Special issue for STOC'14

Computing Marginals Using MapReduce arXiv
Foto Afrati, Shantanu Sharma Jeffrey Ullman, and Jonathan Ullman
Journal of Computer and Systems Science, 2018

An Antifolk Theorem for Large Repeated Games arXiv
Mallesh Pai, Aaron Roth, and Jonathan Ullman
ACM Transactions on Economics and Computation, 2017

Between Pure and Approximate Differential Privacy arXiv
Thomas Steinke and Jonathan Ullman
Journal of Privacy and Confidentiality, 2017

When Can Limited Randomness Be Used in Repeated Games? arXiv
Pavel Hubác̆ek, Moni Naor, and Jonathan Ullman
Theory of Computing Systems, 2016
Special issue for SAGT'15

Answering n^2+o(1) Counting Queries with Differential Privacy is Hard arXiv
Jonathan Ullman
SIAM Journal on Computing, 2016
Special issue for STOC'13

Privately Releasing Conjunctions and the Statistical Query Barrier arXiv
Anupam Gupta, Moritz Hardt, Aaron Roth, and Jonathan Ullman
SIAM Journal on Computing, 2013

Surveys and Other Writing

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