I'm an Assistant Professor of Computer Science at Northeastern University.

Updates

Contact

jullman@ccs.neu.edu

623 ISEC
805 Columbus Avenue
Khoury College of Computer Sciences
Northeastern University
Boston, MA 02118
Map Directions
Bio
CV
Google Scholar

Research

I am a theoretical computer scientist. The focus of my research is how to make data analysis more reliable and better aligned with societal values. A particular focus of mine is statistical data privacy, which studies how and when we can analyze a dataset without revealing information about the individuals in that dataset. I am also interesting in how to prevent false discovery in the empirical sciences. I study these and other questions using tools from cryptography, machine learning, algorithms, and game theory.

My research has been generously funded by the National Science Foundation and Google.

Advising

I am fortunate to work with a number of talented students and postdocs. My current group consists of:


Teaching

I've taught a number of courses, including:

Service

I have served on the program committees of many conferences, including: FOCS '18, SODA '18, TCC '16b, EC '16, TCC '15, STOC '15, and ITCS '15.

I also organize the Workshop on Theory and Practice of Differential Privacy

Students and Advising

I have been fortunate to work with a number of talented students and postdocs.


Service



  • Organizer
  • Program Committee Member
    • IEEE Symposium on Foundations of Computer Science (FOCS) 2018
    • SIAM Symposium on Discrete Algorithms (SODA) 2018
    • ACM Conference on Economics and Computation (EC) 2016
    • Theory of Cryptography Conference (TCC) 2015, 2016
    • ACM Symposium on Theory of Computing (STOC) 2015
    • Innovations in Theoretical Computer Science (ITCS) 2015
  • Reviewer
    • International Conference on Machine Learning (ICML) 2018
    • International Conference on Artificial Intelligence and Statistics (AISTATS) 2017
    • Conference on Neural and Information Processing Systems (NeurIPS) 2016, 2017

Research Papers

Each list is in reverse chronological order.


  • Manuscripts
  • Conference Publications
    • The Structure of Optimal Private Tests for Simple Hypotheses arXiv
      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'16)
    • 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 Hubá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 n2+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
    • 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 Hubác̆ek, Moni Naor, and Jonathan Ullman
      Theory of Computing Systems, 2016
      Special issue for SAGT'15
    • Answering n2+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
  • Workshop Publications
    • Distributed Differential Privacy via Shuffling arXiv
      Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev
      Workshop on Theory and Practice of Differential Privacy (TPDP'18)
    • Privately Learning High-Dimensional Distributions arXiv Talk Video
      Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman
      Workshop on Theory and Practice of Differential Privacy (TPDP'18)
    • Local Differential Privacy for Evolving Data arXiv
      Matthew Joseph, Aaron Roth, Jonathan Ullman, and Bo Waggoner
      Workshop on Theory and Practice of Differential Privacy (TPDP'18)
      Selected for a Contributed Talk
    • Competitive Differentially Private Algorithms for Interactive Queries
      Aleksandar Nikolov and Jonathan Ullman
      Workshop on Theory and Practice of Differential Privacy (TPDP'17)
    • Some Pairs Problems arXiv
      Jeffrey D. Ullman and Jonathan Ullman
      ACM Workshop on Algorithms and Systems for MapReduce and Beyond (BeyondMR'16)
    • Make Up Your Mind: The Price of Online Queries in Differential Privacy arXiv
      Mark Bun, Thomas Steinke, and Jonathan Ullman
      Workshop on Theory and Practice of Differential Privacy (TPDP'16)
      Selected for a Contributed Talk
    • Between Pure and Approximate Differential Privacy arXiv
      Thomas Steinke and Jonathan Ullman
      Workshop on Theory and Practice of Differential Privacy (TPDP'15)
    • On the Zero-Error Capacity Threshold for Deletion Channels arXiv
      Ian Kash, Michael Mitzenmacher, Justin Thaler, and Jonathan Ullman
      Information Theory and Applications Workshop (ITA'11)
  • Surveys and Other Writings
    • 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