Shay Moran

Alon, Caroline, Ann, Shay, and Ella

I am an Associate Professor at the Technion's Faculty of Mathematics. Additionally, I hold affiliations with the Faculties of Computer Science and Data and Decision Sciences. I am also honored to be affiliated with Google Research in Tel Aviv.

My email is: smoran@technion.ac.il

Research interests

Research Group

Current

• Bogdan Chornomaz, Postdoc
• Yair Ashlagi, PhD (co-advised with Roi Livni)
• Vanessa Kosoy, PhD
• Liza Nesterova, PhD (co-advised with Yuval Filmus)
• Hilla Schefler, PhD
• Alexander Shlimovich, PhD
• Tom Waknine, PhD

Past

• Iska Tsubari (Master, 2025)
• Idan Mehalel (PhD, co-advised with Yuval Filmus, 2024)
• Zachary Chase (Postdoc, 2024)
• Simone Fioravanti (Intern, 2023)
• Jonathan Shafer (Intern, 2022, 2023)

Selected Work

For the full list, see complete publication list.

Didactic / Recreational Mathematics

• Diagonalization Games
  Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, and Shlomo Moran
  American Mathematical Monthly (AMM), 2024
  Studies an elementary combinatorial game inspired by Cantor’s diagonalization argument.
• Elementary Derivations of the Euclidean Hurwitz Algebras
  Tomer Moran, Shay Moran, and Shlomo Moran
  American Mathematical Monthly (AMM), 2021
  A particularly meaningful 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 (Gadi’s grandson), Shlomo Moran (my dad), and myself.

Recent Work

• 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
  Manuscript, 2025
• Optimal Mistake Bounds for Transductive Online Learning
  Zachary Chase, Steve Hanneke, Shay Moran, and Jonathan Shafer
  NeurIPS 2025
  Best Paper Runner-Up Award · Oral Presentation
• Reconstruction and Secrecy under Approximate Distance Queries
  Shay Moran and Elizaveta Nesterova
  NeurIPS 2025
  Spotlight
• On Reductions and Representations of Learning Problems in Euclidean Spaces
  Bogdan Chornomaz, Shay Moran, and Tom Waknine
  STOC 2025
• On Differentially Private Linear Algebra
  Haim Kaplan, Yishay Mansour, Shay Moran, Uri Stemmer, and Nitzan Tur
  STOC 2025
• Local Borsuk-Ulam, Stability, and Replicability
  Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff
  STOC 2024
• Ramsey Theorems for Trees and a General `Private Learning Implies Online Learning' Theorem
  Simone Fioravanti, Steve Hanneke, Shay Moran, Hilla Schefler, and Iska Tsubari
  FOCS 2024

Older Work

• 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
• 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
• Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
  Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev
  STOC 2021
  Invited and accepted to STOC special issue of SICOMP
• 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
• A Theory of PAC Learnability of Partial Concept Classes
  Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran
  FOCS 2021
• An Equivalence Between Private Classification and Online Prediction
  Mark Bun, Roi Livni, and Shay Moran
  FOCS 2020
  Best Paper Award · Journal version: Private and Online Learnability are Equivalent (JACM 2022, with authors Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran; merging this paper with the STOC 2019 paper Private PAC Learning Implies Finite Littlestone Dimension ) · Invited talk at TCS+ 2020 · Plenary talk at TPDP 2020 · Invited to HALG 2021
• 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
• Learnability can be undecidable
  Shai Ben-David, Pavel Hrubes, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  Nature Machine Intelligence, 2019
  STOC 2021 (invited paper)
• Near-optimal linear decision trees for k-SUM and related problems
  Daniel Kane, Shachar Lovett, and Shay Moran
  STOC 2018
  Invited to STOC special issue of SICOMP (declined in favor of J. ACM) · Invited talks at TCS+ 2018 and HALG 2019
• 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”