headshot

Jonathan Shafer

I am a researcher. I work in theoretical computer science, and I'm especially fascinated with computational and statistical learning theory.


I am currently a postdoctoral associate at MIT, hosted by Vinod Vaikuntanathan. I also co-organize the ML+Cryptography Seminar. Previously, I earned a PhD from UC Berkeley advised by Shafi Goldwasser, and an MSc from Tel Aviv University advised by Amir Shpilka and Amir Yehudayoff. I completed my undergraduate studies at the Lautman Interdisciplinary Program.

Publications

& Preprints

  1. Optimal Mistake Bounds for Transductive Online Learning

    With Zachary Chase, Steve Hanneke and Shay Moran

  2. Protocols for Verifying Smooth Strategies in Bandits and Games

    With Miranda Christ and Daniel Reichman

  3. Which Algorithms Have Tight Generalization Bounds?

    With Michael Gastpar, Ido Nachum and Thomas Weinberger

  4. Oblivious Defense in ML Models: Backdoor Removal without Detection

    With Shafi Goldwasser, Neekon Vafa and Vinod Vaikuntanathan

    • Conference version: 57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    • Video: pre-recorded talk at STOC, June 2025
    • Video, abstract and slides: talk at the Simons Institute for the Theory of Computing, October 15th 2024
    • Video: talk at the Crypto Seminar at Carnegie Mellon University, February 27th 2025
    • Also presented at the Crypto Seminar at Bar-Ilan University, January 9th 2025; the Theory Seminar at Tel Aviv University, January 28th 2025; the Statistics Seminar at Haifa University, January 29th 2025; the BUSec Seminar at Boston University, April 23rd 2025; and the Theory Seminar at Cornell University, May 12th 2025

  5. Fantastic Generalization Measures are Nowhere to be Found

    With Michael Gastpar, Ido Nachum and Thomas Weinberger

    • Conference version: 12th International Conference on Learning Representations (ICLR 2024)
    • Video, slides: Ido presenting at ICLR, May 8th 2024
    • Poster: designed by Thomas for ICLR

  6. A Trichotomy for Transductive Online Learning

    With Steve Hanneke and Shay Moran

    • Conference version: 37th Annual Conference on Neural Information Processing System (NeurIPS 2023)
    • Video, slides: talk at NeurIPS, December 10th 2023

  7. The Bayesian Stability Zoo

    With Shay Moran and Hilla Schefler

  8. Fine-Grained Distribution-Dependent Learning Curves

    With Olivier Bousquet, Steve Hanneke, Shay Moran and Ilya Tolstikhin

  9. PAC Verification of Statistical Algorithms

    With Saachi Mutreja

  10. Interactive Proofs for Verifying Machine Learning

    With Shafi Goldwasser, Guy Rothblum and Amir Yehudayoff

    • Video: Shafi presenting as part of her invited talk at NeurIPS, December 8th 2020
    • Conference version: 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
    • Video, slides: talk at ITCS, January 8th 2021
    • Also presented at the Charles River Crypto Day, July 31st 2020; the Theory Seminar at Weizmann Institute of Science, January 19th 2020; and the Theory Seminar at Tel Aviv University, January 16th 2020

  11. A Direct Sum Result for the Information Complexity of Learning

    With Ido Nachum and Amir Yehudayoff

  12. Learners that Use Little Information

    With Raef Bassily, Shay Moran, Ido Nachum, and Amir Yehudayoff

    • Conference version: 29th International Conference on Algorithmic Learning Theory (ALT 2018)

Teaching

  1. A Short Introduction to Learning Theory

    Instructor

    A-PIC 2025 — African Summer School on Probability, Information, Computing

    • Notes: Lectures delivered by Jonathan and scribed by Maren Dück

  2. Computational Learning Theory

    Co-Instructor

    UC Berkeley, CS 294-220, Spring 2021

  3. Computability and Complexity

    Teaching Assistant

    UC Berkeley, CS 172, Spring 2019

    • Notes: Discussions delivered and scribed by Jonathan

  4. Algorithms for Computational Linguistics

    Instructor

    Tel Aviv University, 0627-2235-01, Spring 2017
    Replaced a professor that was on sabbatical

    • Notes: Lectures delivered and scribed by Jonathan (Hebrew)

  5. Computational Linguistics for Beginners

    Teaching Assistant

    Tel Aviv University, 0627-2221-01, Spring 2016

  6. Advanced Computational Linguistics

    Teaching Assistant

    Tel Aviv University, 0627-4090-02, Fall 2015

    • Notes: Discussions delivered by Jonathan and scribed by Noa Peled (Hebrew)

Contact