Shay Moran

Shay Moran

I am an Associate Professor affiliated with the Faculty of Mathematics, Faculty of Computer Science, and Faculty of Data and Decision Sciences at the Technion – Israel Institute of Technology, and with Google Research in Tel Aviv.

smoran@technion.ac.il

Shay Moran seated outdoors with Alon, Caroline, Ann, and Ella
Alon, Caroline, Ann, Shay, and Ella.

Research

Mathematical foundations of learning

I study the mathematical foundations of learning, with a focus on generalization and regret bounds. I am also interested in the foundations of responsible and aligned learning.

People

Research group

Current members

Former members

Publications

Recent work

Newest first · Read down the left column, then the right

Complete publication list

  1. Sorting from Counterexamples

    Noga Alon, Shay Moran, and Shlomo Moran

    Manuscript, 2026

    arXivPDF

  2. Optimal Reconstruction from Linear Queries

    Yuval Filmus, Shay Moran, and Elizaveta Nesterova

    COLT 2026

    Best Paper Award
    arXivPDF

  3. Scale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale

    Shashaank Aiyer, Yishay Mansour, Shay Moran, Han Shao, and Tom Waknine

    Manuscript, 2026

    arXivPDF

  4. Strategic PAC Learnability via Geometric Definability

    Yuval Filmus, Shay Moran, Elizaveta Nesterova, Nir Rosenfeld, and Alexander Shlimovich

    Manuscript, 2026

    arXivPDF

  5. An Optimal Sauer Lemma Over k-ary Alphabets

    Steve Hanneke, Qinglin Meng, Shay Moran, and Amirreza Shaeiri

    Manuscript, 2026

    arXivPDF

  6. Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

    Steve Hanneke, Idan Mehalel, and Shay Moran

    FOCS 2026

    arXivPDF

  7. We Should Separate Memorization from Copyright

    Adi Haviv, Niva Elkin-Koren, Uri Hacohen, Roi Livni, and Shay Moran

    Manuscript, 2026

    arXivPDF

  8. Optimal Mistake Bounds for Transductive Online Learning

    Zachary Chase, Steve Hanneke, Shay Moran, and Jonathan Shafer

    NeurIPS 2025

    Best Paper Runner-Up AwardOral Presentation
    arXivPDF

  9. Sample Complexity of Agnostic Multiclass Classification: Natarajan Dimension Strikes Back

    Alon Cohen, Liad Erez, Steve Hanneke, Tomer Koren, Yishay Mansour, Shay Moran, and Qian Zhang

    STOC 2026

    arXivPDF

Selected work

Newest first · Read down the left column, then the right

  1. Credit Attribution and Stable Compression

    Roi Livni, Shay Moran, Kobbi Nissim, and Chirag Pabbaraju

    NeurIPS 2024

    arXivPDF

  2. A Characterization of Multiclass Learnability

    Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, and Amir Yehudayoff

    FOCS 2022

    Invited to FOCS special issue of SICOMP · Invited talk at TCS+ 2022

    arXivPDF

  3. A Theory of Universal Learning

    Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, and Amir Yehudayoff

    STOC 2021

    Invited talk at TCS+ 2021 · Invited to HALG 2022

    arXivPDF

  4. Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games

    Steve Hanneke, Roi Livni, and Shay Moran

    COLT 2021

    Best Paper Runner-Up Award
    arXivPDF

  5. An Equivalence Between Private Classification and Online Prediction

    Mark Bun, Roi Livni, and Shay Moran

    FOCS 2020

    Best Paper Award

    Invited to JACM · Invited talk at TCS+ 2020 · Plenary talk at TPDP 2020 · Invited to HALG 2021

    arXivPDF

  6. Proper Learning, Helly Number, and an Optimal SVM Bound

    Olivier Bousquet, Steve Hanneke, Shay Moran, and Nikita Zhivotovskiy

    COLT 2020

    Best Paper Award

    Invited to Journal of Mathematical Statistics and Learning · Invited to HALG 2021

    arXivPDF

  7. Learnability can be undecidable

    Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff

    Nature Machine Intelligence, 2019

    STOC 2021 (invited paper)

    Publisher

  8. Sign rank, VC dimension and spectral gaps

    Noga Alon, Shay Moran, and Amir Yehudayoff

    In a special issue for the 150th anniversary of Sbornik: Mathematics, 2017

    ECCC

  9. Sample compression schemes for VC classes

    Shay Moran and Amir Yehudayoff

    Journal of the ACM, 2016

    Final Award for Outstanding Paper in the Field of Machine Learning
    ECCC

Beyond research papers

Expository & recreational mathematics

  1. Diagonalization Games

    Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

    American Mathematical Monthly (AMM) 2024

    Studies an elementary combinatorial game inspired by Cantor's diagonalization argument.

    arXivPDF

  2. Elementary Derivations of the Euclidean Hurwitz Algebras

    Tomer Moran, Shay Moran, and Shlomo Moran

    American Mathematical Monthly (AMM) 2021

    A family project completing the last work of my late uncle Gadi Moran, initiated by Gadi's son Arik, with the technical development carried out by Tomer Moran, Shlomo Moran, and me.

    arXivPDF