All publications

Manuscripts

Conference publications

  • 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
  • Beyond Worst-Case Analysis of Sample Complexity for Revenue Maximization via Learning Curves
    Steve Hanneke, Alkis Kalavasis, Shay Moran, and Grigoris Velegkas
    STOC 2026
  • 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
  • Data Selection for ERMs
    Steve Hanneke, Shay Moran, Alexander Shlimovich, and Amir Yehudayoff
    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

    Theses