Jonathan Ullman

Assistant Professor
College of Computer and Information Sciences
Northeastern University

623 ISEC
805 Columbus Ave
Boston, MA, 02118

e-mail: jullman [at] ccs [dot] neu [dot] edu

About Me

I am interested in theoretical computer science broadly. Much of my work addresses with questions like when and how can we analyze a dataset while ensuring privacy for the individuals in the dataset and how can we prevent false discovery in the empirical sciences. I study these questions and others using tools from cryptography, computational learning theory, algorithms, and game theory. You can learn more from this research statement.

Since Fall 2015, I have been an assistant professor in the College of Computer and Information Sciences at Northeastern University, where I am affiliated with Northeastern's Theory Group and the Cybersecurity and Privacy Institute. I am also a senior researcher on the Harvard University Privacy Tools Project. My research has been recognized with an NSF CAREER award and a Google Faculty Research Award.

Prior to joining Northeastern I completed my PhD at Harvard University under the supervision of Salil Vadhan. I was also a postdoctoral fellow in the Center for Research on Computation and Society and in the inaugural class of junior fellows in the Simons Society of Fellows.

If you are a bright and motivated student interested in theoretical computer science, I highly encourage you to apply to Northeastern! See here for more information.




Recent/Selected Research Papers   [All Papers]All Research Papers   [Selected Papers]   [Google Scholar]

  • Tight Lower Bounds for Locally Differentially Private Selection
    Jonathan Ullman
  • Subgaussian Concentration via Stability Arguments
    Thomas Steinke, Jonathan Ullman
  • The Structure of Optimal Private Tests for Simple Hypotheses
    Clément Canonne, Gautam Kamath, Audra McMillan, Adam Smith, Jonathan Ullman
  • Local Differential Privacy for Evolving Data
    Matthew Joseph, Aaron Roth, Jonathan Ullman, Bo Waggoner
    NIPS 2018 (Spotlight Presenation); TPDP 2018
  • The Limits of Post-Selection Generalization
    Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, Jonathan Ullman
    NIPS 2018
  • Distributed Differential Privacy via Mixnets
    Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber Maxim Zhilyaev
    TPDP 2018
  • Privately Learning High-Dimensional Distributions
    Gautam Kamath, Jerry Li, Vikrant Singhal, Jonathan Ullman
    TPDP 2018
  • Hardness of Non-Interactive Differential Privacy from One-Way Functions
    Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, Daniel Wichs
    CRYPTO 2018
  • Skyline Identification in Multi-Armed Bandits
    Albert Cheu, Ravi Sundaram, Jonathan Ullman
    ISIT 2018
  • Tight Bounds for Differentially Private Selection
    Thomas Steinke, Jonathan Ullman
    FOCS 2017
  • Fractional Set Cover in the Streaming Model
    Piotr Indyk, Sepideh Mahabadi, Ronitt Rubinfeld, Jonathan Ullman, Ali Vakilian, Anak Yodpinyanee
    APPROX 2017
  • The Price of Selection in Differential Privacy
    Mitali Bafna, Jonathan Ullman
    COLT 2017
  • Multidimensional Dynamic Pricing for Welfare Maximization
    Aaron Roth, Aleksandrs Slivkins, Jonathan Ullman, Zhiwei Steven Wu
    EC 2017; Invited to the special issue of TEAC
  • Make Up Your Mind: The Price of Online Queries in Differential Privacy
    Mark Bun, Thomas Steinke, Jonathan Ullman
    SODA 2017; TPDP 2016
  • Computing Marginals Using MapReduce
    Foto Afrati, Shantanu Sharma, Jeffrey D. Ullman, Jonathan Ullman
    IDEAS 2016
  • Exposed! A Survey of Attacks on Private Data
    Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman
    Annual Review of Statistics and its Applications
  • Privacy Odometers and Filters: Pay-as-you-Go Composition
    Ryan Rogers, Aaron Roth, Jonathan Ullman, Salil Vadhan
    NIPS 2016
  • Strong Hardness of Privacy from Weak Traitor Tracing
    Lucas Kowalczyk, Tal Malkin, Jonathan Ullman, Mark Zhandry
    TCC 2016B
  • An Anti-Folk Theorem for Large Repeated Games with Imperfect Monitoring
    Mallesh Pai, Aaron Roth, Jonathan Ullman
    Transactions on Economics and Computation
  • Some Pairs Problems
    Jeffrey D. Ullman, Jonathan Ullman
    BeyondMR 2016
  • Space Lower Bounds for Itemset Frequency Sketches
    Edo Liberty, Michael Mitzenmacher, Justin Thaler, Jonathan Ullman
    PODS 2016
  • Algorithmic Stability for Adaptive Data Analysis
    Raef Bassily, Kobbi Nissim, Uri Stemmer, Adam Smith, Thomas Steinke, Jonathan Ullman
    STOC 2016; Invited to the special issue of SICOMP
  • Watch and Learn: Optimizing from Revealed Preferences Feedback
    Aaron Roth, Jonathan Ullman, Zhiwei Steven Wu
    STOC 2016
  • When Can Limited Randomness Be Used in Repeated Games?
    Pavel Hubacek, Moni Naor, Jonathan Ullman
    SAGT 2015; TCS special issue for selected papers from SAGT 2014/15
  • Robust Traceability from Trace Amounts
    Cynthia Dwork, Adam Smith, Thomas Steinke, Jonathan Ullman, Salil Vadhan
    FOCS 2015
  • Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
    Thomas Steinke, Jonathan Ullman
    COLT 2015
  • Inducing Approximately Optimal Flow Using Truthful Mediators
    Ryan Rogers, Aaron Roth, Jonathan Ullman, Zhiwei Steven Wu
    EC 2015
  • Between Pure and Approximate Differential Privacy
    Thomas Steinke, Jonathan Ullman
    TPDP 2015; Journal of Privacy and Confidentiality
  • Private Multiplicative Weights Beyond Linear Queries
    Jonathan Ullman
    PODS 2015
  • Preventing False Discovery in Interactive Data Analysis is Hard
    Moritz Hardt, Jonathan Ullman
    FOCS 2014
  • Privately Solving Linear Programs
    Justin Hsu, Aaron Roth, Tim Roughgarden, Jonathan Ullman
    ICALP 2014 Track A
  • Fingerprinting Codes and the Price of Approximate Differential Privacy
    Mark Bun, Jonathan Ullman, Salil Vadhan
    STOC 2014; SICOMP special issue for selected papers from STOC 2014
  • Faster Private Release of Marginals on Small Databases
    Karthekeyan Chandrasekaran, Justin Thaler, Jonathan Ullman, Andrew Wan
    ITCS 2014
  • Robust Mediators in Large Games
    Michael Kearns, Mallesh Pai, Ryan Rogers, Aaron Roth, Jonathan Ullman
    ITCS 2014
  • Differential Privacy for the Analyst via Private Equilibrium Computation
    Justin Hsu, Aaron Roth, Jonathan Ullman
    STOC 2013
  • Answering n2+o(1) Counting Queries with Differential Privacy is Hard
    Jonathan Ullman
    STOC 2013; SICOMP special issue for selected papers from STOC 2013
  • Faster Algorithms for Privately Releasing Marginals
    Justin Thaler, Jonathan Ullman, Salil Vadhan
    ICALP 2012 Track A
  • Iterative Constructions and Private Data Release
    Anupam Gupta, Aaron Roth, Jonathan Ullman
    TCC 2012
  • On the Zero-Error Capacity Threshold for Deletion Channels
    Ian Kash, Michael Mitzenmacher, Justin Thaler, Jonathan Ullman
    ITA 2011
  • Privately Releasing Conjunctions and the Statistical Query Barrier
    Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan Ullman
    STOC 2011; SICOMP
  • PCPs and the Hardness of Generating Private Synthetic Data
    Jonathan Ullman, Salil Vadhan
    TCC 2011; Invited to the Journal of Cryptology
  • Course Allocation by Proxy Auction
    Scott Kominers, Mike Ruberry, Jonathan Ullman
    WINE 2010
  • The Price of Privately Releasing Contingency Tables and the Spectra of Random Matrices with Correlated Rows
    Shiva Kasiviswanathan, Mark Rudelson, Adam Smith, Jonathan Ullman
    STOC 2010

Academic Service

Last Updated

5 Sep 2018.