Research archive
Publications
Find a publication
No publications found
Try a broader search or clear the filters.
2026
Back to filtersScale-Sensitive Shattering: Learnability and Evaluability at Optimal Scale
- Preprint Manuscript, 2026
PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting
- Preprint Manuscript, 2026
Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
- Conference FOCS 2026
A Theoretical Framework for Statistical Evaluability of Generative Models
- Conference ICML 2026
2025
Back to filtersOptimal Mistake Bounds for Transductive Online Learning
Best Paper Runner-Up AwardOral Presentation
- Conference NeurIPS 2025
Agnostic Learning under Targeted Poisoning: Optimal Rates and the Role of Randomness
- Conference NeurIPS 2025 Spotlight
Reconstruction and Secrecy under Approximate Distance Queries
- Conference NeurIPS 2025 Spotlight
Marginal-Nonuniform PAC Learnability
- Conference NeurIPS 2025
A fine-grained characterization of PAC learnability
- Conference COLT 2025
On Reductions and Representations of Learning Problems in Euclidean Spaces
- Conference STOC 2025
Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension
- Journal SICOMP 2025 (conference version at COLT 2023)
- Conference COLT 2023
The unstable formula theorem revisited via algorithms
- Journal Accepted to Annals of Pure and Applied Logic 2025
2024
Back to filtersBandit-Feedback Online Multiclass Classification: Variants and Tradeoffs
- Conference NeurIPS 2024
Universal Rates for Active Learning
- Conference NeurIPS 2024
Improved Sample Complexity for Multiclass PAC Learning
- Conference NeurIPS 2024
Agnostic Online Learning and Excellent Sets
- Journal Transactions of the American Mathematical Society 2024
2023
Back to filtersMulticlass Boosting: Simple and Intuitive Weak Learning Criteria
- Conference NeurIPS 2023
Improper Multiclass Boosting
- Conference COLT 2023
Universal Rates for Multiclass Learning
- Conference COLT 2023
Boosting Simple Learners
- Journal TheoretiCS 2023 (conference version at STOC 2021)
- Conference STOC 2021
Adversarial Laws of Large Numbers and Optimal Regret in Online Classification
- Journal SICOMP 2023 (conference version at STOC 2021)
- Conference STOC 2021 Invited and accepted to STOC special issue of SICOMP
2022
Back to filtersUniversal Rates for Interactive Learning
Oral Presentation
- Conference NeurIPS 2022
A Characterization of Multiclass Learnability
- Conference FOCS 2022 Invited to FOCS special issue of SICOMP · Invited talk at TCS+ 2022
Understanding Generalization via Leave-One-Out Conditional Mutual Information
- Conference ISIT 2022
Uniform Brackets, Containers, and Combinatorial Macbeath Regions
- Conference ITCS 2022
Private and Online Learnability are Equivalent
- Journal 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)
2021
Back to filtersTowards a Unified Information-Theoretic Framework for Generalization
Spotlight Presentation
- Conference NeurIPS 2021
Multiclass Boosting and the Cost of Weak Learning
- Conference NeurIPS 2021
Online Learning with Simple Predictors and a Combinatorial Characterization of Minimax in 0/1 Games
Best Paper Runner-Up Award
- Conference COLT 2021
Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility
- Conference COLT 2021
A Theory of Universal Learning
- Conference STOC 2021 Invited talk at TCS+ 2021 · Invited to HALG 2022
Elementary Derivations of the Euclidean Hurwitz Algebras
- Journal American Mathematical Monthly (AMM) 2021
2020
Back to filtersOn the Information Complexity of Proper Learners for VC Classes in the Realizable Case
- Preprint Manuscript, 2020
An Equivalence Between Private Classification and Online Prediction
Best Paper Award
- Conference FOCS 2020 Invited to JACM · Invited talk at TCS+ 2020 · Plenary talk at TPDP 2020 · Invited to HALG 2021
Private Query Release Assisted by Public Data
- Conference ICML 2020 Plenary talk at TPDP 2020
Proper Learning, Helly Number, and an Optimal SVM Bound
Best Paper Award
- Conference COLT 2020 Invited to Journal of Mathematical Statistics and Learning · Invited to HALG 2021
Closure Properties for Private Classification and Online Prediction
- Conference COLT 2020, TPDP 2020
On weak epsilon-nets and the Radon number
- Journal Discrete & Computational Geometry (DCG) 2020
- Conference SoCG 2019 Invited and accepted to a special issue of Discrete & Computational Geometry (DCG)
A Sauer-Shelah-Perles Lemma for Lattices
- Journal The Electronic Journal of Combinatorics, 2020
2019
Back to filtersPrivate Learning implies Online Learning: An Efficient Reduction
Spotlight Presentation
- Conference NeurIPS 2019
Private PAC learning implies finite Littlestone dimension
- Conference STOC 2019 Plenary presentation at the "Theory and Practice of Differential Privacy 2018" workshop
Near-optimal linear decision trees for k-SUM and related problems
- Journal Journal of the ACM, 2019
- Conference STOC 2018 Invited to STOC special issue of SICOMP (declined in favor of J. ACM) · Invited talks at TCS+ 2018 and HALG 2019
Twenty (short) questions
- Journal Combinatorica, 2019
- Conference STOC 2017 Twenty (simple) questionsInvited to HALG 2018
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound
- Journal Computational Complexity
- Conference ICALP 2014
Learnability can be undecidable
- Journal Nature Machine Intelligence, 2019 STOC 2021 (invited paper)
2018
Back to filters2017
Back to filtersSubmultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues
Spotlight Presentation
- Conference NIPS 2017
Sign rank, VC dimension and spectral gaps
- Journal In a special issue for the 150th anniversary of Sbornik: Mathematics, 2017
- Conference COLT 2016
Teaching and compressing for low VC dimension
- Journal In "A Journey Through Discrete Mathematics: A Tribute to Jiri Matousek", 2017
- Conference 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
2016
Back to filtersDirect sum fails for zero error average communication
- Journal Algorithmica, 2016
- Conference ITCS 2014 Invited to a special issue of Algorithmica
Sample compression schemes for VC classes
Final Award for Outstanding Paper in the Field of Machine Learning
- Journal Journal of the ACM, 2016
Simple and Optimal Fault-Tolerant Rumor Spreading
- Journal Distributed Computing, Springer, 2016
2015
Back to filtersMatchings vs hitting sets among half-spaces in low dimensional euclidean spaces
- Preprint Manuscript, 2015
2013
Back to filtersShattering, Graph Orientations, and Connectivity
- Journal The Electronic Journal of Combinatorics, 2013