All publications

Conference publications

• 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
• Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
  Bogdan Chornomaz, Yonatan Koren, Shay Moran, and Tom Waknine
  NeurIPS 2025
  Spotlight
• Reconstruction and Secrecy under Approximate Distance Queries
  Shay Moran and Elizaveta Nesterova
  NeurIPS 2025
  Spotlight
• Marginal-Nonuniform PAC Learnability
  Steve Hanneke, Shay Moran, and Maximilian Thiessen
  NeurIPS 2025
• Probably Approximately Precision and Recall Learning
  Lee Cohen, Yishay Mansour, Shay Moran, and Han Shao
  NeurIPS 2025
• The Role of Randomness in Stability
  Max Hopkins and Shay Moran
  ICML 2025
  Spotlight
• Spherical Dimension
  Bogdan Chornomaz, Shay Moran, Tom Waknine
  COLT 2025
• Private List Learnability vs. Online List Learnability
  Steve Hanneke, Shay Moran, Hilla Schefler, Iska Tsubari
  COLT 2025
• A fine-grained characterization of PAC learnability
  Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen
  COLT 2025
• Of Dice and Games: A Theory of Generalized Boosting
  Marco Bressan, Nataly Brukhim, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen
  COLT 2025
• 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
• Can Copyright Be Reduced to Privacy?
  Niva Elkin-Koren, Uri Hacohen, Roi Livni, and Shay Moran
  FORC 2024
• Data Reconstruction: When You See It and When You Don't
  Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia
  ITCS 2024
• Bandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
  Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran
  NeurIPS 2024
• Universal Rates for Active Learning
  Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas
  NeurIPS 2024
• Improved Sample Complexity for Multiclass PAC Learning
  Steve Hanneke, Shay Moran, and Qiang Zhang
  NeurIPS 2024
• Learning-Augmented Algorithms with Explicit Predictors
  Marek Elias, Haim Kaplan, Yishay Mansour, and Shay Moran
  NeurIPS 2024
• Fast Rates for Bandit PAC Multiclass Classification
  Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran
  NeurIPS 2024
• Credit Attribution and Stable Compression
  Roi Livni, Shay Moran, Kobbi Nissim, and Chirag Pabbaraju
  NeurIPS 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
• Local Borsuk-Ulam, Stability, and Replicability
  Zachary Chase, Bogdan Chornomaz, Shay Moran, and Amir Yehudayoff
  STOC 2024
• The Real Price of Bandit Information in Multiclass Classification
  Liad Erez, Alon Cohen, Tomer Koren, Yishay Mansour, and Shay Moran
  COLT 2024
• List Sample Compression and Uniform Convergence
  Steve Hanneke, Shay Moran, Tom Waknine
  COLT 2024
• Learnability Gaps of Strategic Classification
  Lee Cohen, Yishay Mansour, Shay Moran, Han Shao
  COLT 2024
• Dual VC Dimension Obstructs Sample Compression by Embeddings
  Zachary Chase, Bogdan Chornomaz, Steve Hanneke, Shay Moran, and Amir Yehudayoff
  COLT 2024
• A Theory of Interpretable Approximations
  Marco Bressan, Nicolò Cesa-Bianchi, Emmanuel Esposito, Yishay Mansour, Shay Moran, and Maximilian Thiessen
  COLT 2024
• A Unified Characterization of Private Learnability via Graph Theory
  Noga Alon, Shay Moran, Hilla Schefler, and Amir Yehudayoff
  COLT 2024
• Replicability and stability in learning
  Zachary Chase, Shay Moran, and Amir Yehudayoff
  FOCS 2023
• Adversarial Resilience in Sequential Prediction via Abstention
  Surbhi Goel, Steve Hanneke, Shay Moran, Abhishek Shetty
  NeurIPS 2023
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria
  Nataly Brukhim, Amit Daniely, Yishay Mansour, and Shay Moran
  NeurIPS 2023
• A Trichotomy for Transductive Learning
  Steve Hanneke, Shay Moran, and Jonathan Shafer (should also be here the humble Zachary Chase!)
  NeurIPS 2023
• On Differentially Private Online Prediction
  Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, and Uri Stemmer
  NeurIPS 2023
• The Bayesian Stability Zoo
  Shay Moran, Jonathan Shafer, and Hilla Schefler
  NeurIPS 2023
• Improper Multiclass Boosting
  Nataly Brukhim, Steve Hanneke, and Shay Moran
  COLT 2023
• Multiclass Online Learning and Uniform Convergence
  Steve Hanneke, Shay Moran, Vinod Raman, Unique Subedi, and Amber Tewari
  COLT 2023
• Universal Rates for Multiclass Learning
  Steve Hanneke, Shay Moran, and Qian Zhang
  COLT 2023
• Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
  Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran
  COLT 2023
• List Online Learning
  Shay Moran, Ohad Sharon, Iska Tsubari, and Sivan Yosebashvili
  COLT 2023
• Fine-Grained Distribution-Dependent Learning Curves
  Olivier Bousquet, Steve Hanneke, Shay Moran, Jonathan Shafer, and Ilya Tolstikhin
  COLT 2023
• Statistical Indistinguishability of Learning Algorithms
  Alkis Kalavasis, Amin Karbasi, Shay Moran, Grigoris Velegkas
  ICML 2023
• Universal Rates for Interactive Learning
  Steve Hanneke, Amin Karbasi, Shay Moran, and Grigoris Velegkas
  NeurIPS 2022
  Oral Presentation
• On Optimal Learning Under Targeted Data Poisoning
  Steve Hanneke, Amin Karbasi, Mohammad Mahmoody, Idan Mehalel, and Shay Moran
  NeurIPS 2022
  Oral Presentation
• Integral Probability Metrics PAC-Bayes Bounds
  Ron Amit, Baruch Epstein, Ron Meir, and Shay Moran
  NeurIPS 2022
• 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
• Monotone Learning
  Olivier Bousquet, Amit Daniely, Haim Kaplan, Yishay Mansour, Shay Moran, and Uri Stemmer
  COLT 2022
• A Resiliant Distributed Boosting Algorithm
  Yuval Filmus, Idan Mehalel, Shay Moran
  ICML 2022
• Active Learning with Label Comparisons
  Gal Elidan, Amir Globerson, Shay Moran, and Gal Yona
  UAI 2022
• Uniform Brackets, Containers, and Combinatorial Macbeath Regions
  Kunal Dutta, Arijit Ghosh, and Shay Moran
  ITCS 2022
• Towards a Unified Information-Theoretic Framework for Generalization
  Mahdi Haghifam, Gintare Karolina Dzuigaite, Shay Moran, and Daniel M. Roy
  NeurIPS 2021
  Spotlight Presentation
• Multiclass Boosting and the Cost of Weak Learning
  Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E. Schapire
  NeurIPS 2021
• A Theory of PAC Learnability of Partial Concept Classes
  Noga Alon, Steve Hanneke, Ron Holzman, and Shay Moran
  FOCS 2021
• Statistically Near-Optimal Hypothesis Selection
  Olivier Bousquet, Mark Braverman, Klim Efremenko, Gillat Kol, and Shay Moran
  FOCS 2021
• 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
• Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
  Mark Braverman, Gillat Kol, Shay Moran, and Raghuvansh R. Saxena
  COLT 2021
• Boosting Simple Learners
  Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran
  STOC 2021
• 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
• 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
• The entropy of lies: playing twenty questions with a liar
  Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran
  ITCS 2021
• Learning from Mixtures of Private and Public Populations
  Raef Bassily, Shay Moran, and Anupama Nandi
  NeurIPS 2020
• A Limitation of the PAC-Bayes Framework
  Roi Livni and Shay Moran
  NeurIPS 2020
• Online Agnostic Boosting via Regret Minimization
  Nataly Brukhim, Xinyi Chen, Elad Hazan, and Shay Moran
  NeurIPS 2020
• Synthetic Data Generators - Sequential and Private
  Olivier Bousquet, Roi Livni, and Shay Moran
  NeurIPS 2020
• 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
• Private Query Release Assisted by Public Data
  Raef Bassily, Albert Cheu, Shay Moran, Alexander Nikolov, Jonathan Ullman, and Zhiwey Steven Wu
  ICML 2020
  Plenary talk at TPDP 2020
• 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
• Closure Properties for Private Classification and Online Prediction
  Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer
  COLT 2020, TPDP 2020
• On the Perceptron's Compression
  Shay Moran, Ido Nachum, Itai Panasoff, and Amir Yehudayoff
  CiE 2020
• An adaptive nearest neighbor rule for classification
  Akshay Balsubramani, Sanjoy Dasgupta, Yoav Freund, and Shay Moran
  NeurIPS 2019
  Spotlight Presentation
• Private Learning implies Online Learning: An Efficient Reduction
  Alon Gonen, Elad Hazan, and Shay Moran
  NeurIPS 2019
  Spotlight Presentation
• Limits of Private Learning with Access to Public Data
  Noga Alon, Raef Bassily, and Shay Moran
  NeurIPS 2019
• Learning to Screen
  Alon Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, and Shay Moran
  NeurIPS 2019
• Private Centerpoints and Learning of Halfspaces
  Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer
  COLT 2019
• The Optimal Approximation Factor in Density Estimation
  Olivier Bousquet, Daniel Kane, and Shay Moran
  COLT 2019
• On Communication Complexity of Classification Problems
  Daniel Kane, Roi Livni, Shay Moran, and Amir Yehudayoff
  COLT 2019
• Unlabeled sample compression schemes and corner peelings for ample and maximum classes
  Jeremie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth
  ICALP 2019
• Private PAC learning implies finite Littlestone dimension
  Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran
  STOC 2019
  Plenary presentation at the "Theory and Practice of Differential Privacy 2018" workshop
• On weak epsilon-nets and the Radon number
  Shay Moran and Amir Yehudayoff
  SoCG 2019
  Invited and accepted to a special issue of Discrete & Computational Geometry (DCG)
• Generalized comparison trees for point-location problems
  Daniel Kane, Shachar Lovett, and Shay Moran
  ICALP 2018
• Are Two (Samples) Really Better Than One? On The Non-Asymptotic Performance of Empirical Revenue Maximization
  Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, and Shay Moran
  EC 2018
• 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
• Learners that Leak Little Information
  Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff
  ALT 2018
• Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
  Noga Alon, Moshe Babaioff, Yannai A. Gonczarowski, Yishay Mansour, Shay Moran, and Amir Yehudayoff
  NIPS 2017
  Spotlight Presentation
• Active classification with comparison queries
  Daniel Kane, Shachar Lovett, Shay Moran, and Jiapeng Zhang
  FOCS 2017
• Twenty (simple) questions
  Yuval Dagan, Ariel Gabizon, Yuval Filmus, and Shay Moran
  STOC 2017
  Invited to HALG 2018
• On statistical learning via the lens of compression
  Ofir David, Shay Moran, and Amir Yehudayoff
  NIPS 2016
  Oral Presentation
• Labeled compression schemes for extremal classes
  Shay Moran and Manfred K. Warmuth
  ALT 2016
• Fooling Pairs in Randomized Communication Complexity
  Shay Moran, Makrand Sinha, and Amir Yehudayoff
  SIROCCO 2016
• Hitting set for hypergraphs of low VC-dimension
  Karl Bringmann, László Kozma, Shay Moran, and N.S. Narayanaswami
  ESA 2016
• Shattered Sets and the Hilbert Function
  Shay Moran and Cyrus Rashtchian
  MFCS 2016
• Sign rank, VC dimension and spectral gaps
  Noga Alon, Shay Moran, and Amir Yehudayoff
  COLT 2016
• Node-balancing by edge-increments
  Friedrich Eisenbrand, Shay Moran, Rom Pinchasi, and Martin Skutella
  ESA 2015
• Teaching and compressing for low VC dimension
  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff
  FOCS 2015
  Invited to FOCS special issue of SICOMP (declined in favor of J. ACM)
  The conference version combines two separate papers:

  Teaching and compressing for low VC dimension

  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff

  Sample compression schemes for VC classes

  Shay Moran and Amir Yehudayoff
• Internal compression of protocols to entropy
  Balthazar Bauer, Shay Moran, and Amir Yehudayoff
  RANDOM 2015
• Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  ICALP 2014
• Direct sum fails for zero error average communication
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  ITCS 2014
  Invited to a special issue of Algorithmica

Journal publications

• Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
  Yuval Filmus, Steve Hanneke, Idan Mehalel, and Shay Moran
  SICOMP 2025 (conference version at COLT 2023)
• The unstable formula theorem revisited via algorithms
  Maryanthe Malliaris and Shay Moran
  Accepted to Annals of Pure and Applied Logic 2025
• Diagonalization Games
  Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
  American Mathematical Monthly (AMM) 2024
• Agnostic Online Learning and Excellent Sets
  Maryanthe Malliaris and Shay Moran
  Transactions of the American Mathematical Society 2024
• 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
  SICOMP 2023 (conference version at STOC 2021)
• Boosting Simple Learners
  Noga Alon, Alon Gonen, Elad Hazan, and Shay Moran
  TheoretiCS 2023 (conference version at STOC 2021)
• Private and Online Learnability are Equivalent
  Noga Alon, Mark Bun, Roi Livni, Maryanthe Malliaris, and Shay Moran
  Journal of the ACM, 2022
  Merged journal version of:

  An Equivalence Between Private Classification and Online Prediction

  Mark Bun, Roi Livni, and Shay Moran (FOCS 2020)

  Private PAC Learning Implies Finite Littlestone Dimension

  Noga Alon, Roi Livni, Maryanthe Malliaris, and Shay Moran (STOC 2019)
• Elementary Derivations of the Euclidean Hurwitz Algebras
  Tomer Moran, Shay Moran, and Shlomo Moran
  American Mathematical Monthly (AMM) 2021
• A Sauer-Shelah-Perles Lemma for Lattices
  Stijn Cambie, Bogdan Chornomaz, Zeev Dvir, Yuval Filmus, and Shay Moran
  The Electronic Journal of Combinatorics, 2020
• On weak epsilon-nets and the Radon number
  Shay Moran and Amir Yehudayoff
  Discrete & Computational Geometry (DCG) 2020
• 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
  Journal of the ACM, 2019
• Twenty (short) questions
  Yuval Dagan, Ariel Gabizon, Yuval Filmus, and Shay Moran
  Combinatorica, 2019
• A Sauer-Shelah-Perles Lemma for Sumsets
  Zeev Dvir and Shay Moran
  The Electronic Journal of Combinatorics, 2018
• Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  Computational Complexity
• Teaching and compressing for low VC dimension
  Shay Moran, Amir Shpilka, Avi Wigderson, and Amir Yehudayoff
  In "A Journey Through Discrete Mathematics: A Tribute to Jiri Matousek", 2017
• 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
• 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"
• Direct sum fails for zero error average communication
  Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff
  Algorithmica, 2016
• A note on average-case sorting
  Shay Moran and Amir Yehudayoff
  Order, Springer, 2015
• Simple and Optimal Fault-Tolerant Rumor Spreading
  Benjamin Doerr, Carola Doerr, Shay Moran, and Shlomo Moran
  Distributed Computing, Springer, 2016
• Shattering, Graph Orientations, and Connectivity
  László Kozma and Shay Moran
  The Electronic Journal of Combinatorics, 2013

Manuscripts

• 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
• How Expressive Are Friendly School Partitions
  Josef Minarik, Shay Moran, and Michael Skotnica
• Matchings vs hitting sets among half-spaces in low dimensional euclidean spaces
  Shay Moran and Rom Pinchasi

Theses

• Shattering-Extremal Systems
  Shay Moran
  Masters' thesis
• Generalization and simplification in machine learning
  Shay Moran
  PhD thesis