Shay Moran

Roei Davidson

Nir Grinberg

Proceedings of the Eighteenth International AAAI Conference on Web and Social Media, 2024

Can Copyright Be Reduced to Privacy?

[BibT_eX]

[DOI]

Proceedings of the 5th Symposium on Foundations of Responsible Computing, 2024

Ramsey Theorems for Trees and a General 'Private Learning Implies Online Learning' Theorem.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Open problem: Direct Sums in Learning Theory.

[BibT_eX]

[DOI]

Tom Waknine

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

List Sample Compression and Uniform Convergence.

[BibT_eX]

[DOI]

Tom Waknine

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

The Real Price of Bandit Information in Multiclass Classification.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

A Unified Characterization of Private Learnability via Graph Theory.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

A Theory of Interpretable Approximations.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Learnability Gaps of Strategic Classification.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Dual VC Dimension Obstructs Sample Compression by Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Boosting Simple Learners.

[BibT_eX]

[DOI]

TheoretiCS, 2023

Diagonalization Games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Replicability and stability in learning.

[BibT_eX]

[DOI]

Zachary Chase

CoRR, 2023

List Online Classification.

[BibT_eX]

[DOI]

Ohad Sharon

Iska Tsubari

CoRR, 2023

On Differentially Private Online Predictions.

[BibT_eX]

[DOI]

CoRR, 2023

The Bayesian Stability Zoo.

[BibT_eX]

[DOI]

Hilla Schefler

Jonathan Shafer

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Black-Box Differential Privacy for Interactive ML.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

A Trichotomy for Transductive Online Learning.

[BibT_eX]

[DOI]

Jonathan Shafer

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Adversarial Resilience in Sequential Prediction via Abstention.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Multiclass Boosting: Simple and Intuitive Weak Learning Criteria.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Statistical Indistinguishability of Learning Algorithms.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Stability and Replicability in Learning.

[BibT_eX]

[DOI]

Zachary Chase

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

List Online Classification.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Universal Rates for Multiclass Learning.

[BibT_eX]

[DOI]

Qian Zhang

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Multiclass Online Learning and Uniform Convergence.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Optimal Prediction Using Expert Advice and Randomized Littlestone Dimension.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Improper Multiclass Boosting.

[BibT_eX]

[DOI]

Nataly Brukhim

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Fine-Grained Distribution-Dependent Learning Curves.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Unlabeled sample compression schemes and corner peelings for ample and maximum classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2022

Private and Online Learnability Are Equivalent.

[BibT_eX]

[DOI]

J. ACM, 2022

A Characterization of Multiclass Learnability.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

The unstable formula theorem revisited.

[BibT_eX]

[DOI]

Maryanthe Malliaris

CoRR, 2022

Differentially-Private Bayes Consistency.

[BibT_eX]

[DOI]

CoRR, 2022

How Expressive Are Friendly School Partitions?

[BibT_eX]

[DOI]

Josef Minarík

Michael Skotnica

CoRR, 2022

Active learning with label comparisons.

[BibT_eX]

[DOI]

Proceedings of the Uncertainty in Artificial Intelligence, 2022

Universal Rates for Interactive Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

On Optimal Learning Under Targeted Data Poisoning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Integral Probability Metrics PAC-Bayes Bounds.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Understanding Generalization via Leave-One-Out Conditional Mutual Information.

[BibT_eX]

[DOI]

Mahdi Haghifam

Gintare Karolina Dziugaite

Daniel M. Roy

Proceedings of the IEEE International Symposium on Information Theory, 2022

Uniform Brackets, Containers, and Combinatorial Macbeath Regions.

[BibT_eX]

[DOI]

Kunal Dutta

Arijit Ghosh

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

A Resilient Distributed Boosting Algorithm.

[BibT_eX]

[DOI]

Yuval Filmus

Idan Mehalel

Proceedings of the International Conference on Machine Learning, 2022

Monotone Learning.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2-5 July 2022, London, UK., 2022

2021

Elementary Derivations of the Euclidean Hurwitz Algebras Adapted from Gadi Moran's last paper.

[BibT_eX]

[DOI]

Tomer Moran

Shlomo Moran

Am. Math. Mon., 2021

Agnostic Online Learning and Excellent Sets.

[BibT_eX]

[DOI]

Maryanthe Malliaris

Gintare Karolina Dziugaite

CoRR, 2021

A theory of universal learning.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Learnability can be independent of set theory (invited paper).

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Adversarial laws of large numbers and optimal regret in online classification.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Towards a Unified Information-Theoretic Framework for Generalization.

[BibT_eX]

[DOI]

Mahdi Haghifam

Daniel M. Roy

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Multiclass Boosting and the Cost of Weak Learning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

The Entropy of Lies: Playing Twenty Questions with a Liar.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Statistically Near-Optimal Hypothesis Selection.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

A Theory of PAC Learnability of Partial Concept Classes.

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

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

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

Near Optimal Distributed Learning of Halfspaces with Two Parties.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2021

2020

On Weak ε-Nets and the Radon Number.

[BibT_eX]

[DOI]

Gintare Karolina Dziugaite

Discret. Comput. Geom., 2020

On the Information Complexity of Proper Learners for VC Classes in the Realizable Case.

[BibT_eX]

[DOI]

Mahdi Haghifam

Daniel M. Roy

CoRR, 2020

A Sauer-Shelah-Perles Lemma for Lattices.

[BibT_eX]

[DOI]

Electron. J. Comb., 2020

A Limitation of the PAC-Bayes Framework.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Online Agnostic Boosting via Regret Minimization.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Synthetic Data Generators - Sequential and Private.

[BibT_eX]

[DOI]

Olivier Bousquet

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Learning from Mixtures of Private and Public Populations.

[BibT_eX]

[DOI]

Raef Bassily

Anupama Nandi

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Private Query Release Assisted by Public Data.

[BibT_eX]

[DOI]

Proceedings of the 37th International Conference on Machine Learning, 2020

An Equivalence Between Private Classification and Online Prediction.

[BibT_eX]

[DOI]

Mark Bun

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

Closure Properties for Private Classification and Online Prediction.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

On the Perceptron's Compression.

[BibT_eX]

[DOI]

Proceedings of the Beyond the Horizon of Computability, 2020

2019

Author Correction: Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Learnability can be undecidable.

[BibT_eX]

[DOI]

Nat. Mach. Intell., 2019

Convex Set Disjointness, Distributed Learning of Halfspaces, and LP Feasibility.

[BibT_eX]

[DOI]

CoRR, 2019

Learning and Generalization for Matching Problems.

[BibT_eX]

[DOI]

CoRR, 2019

Passing Tests without Memorizing: Two Models for Fooling Discriminators.

[BibT_eX]

[DOI]

Olivier Bousquet

CoRR, 2019

Twenty (Short) Questions.

[BibT_eX]

[DOI]

Comb., 2019

Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound.

[BibT_eX]

[DOI]

Comput. Complex., 2019

Private PAC learning implies finite Littlestone dimension.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Private Learning Implies Online Learning: An Efficient Reduction.

[BibT_eX]

[DOI]

Alon Gonen

Elad Hazan

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Learning to Screen.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Limits of Private Learning with Access to Public Data.

[BibT_eX]

[DOI]

Raef Bassily

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

An adaptive nearest neighbor rule for classification.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

On Weak epsilon-Nets and the Radon Number.

[BibT_eX]

[DOI]

Proceedings of the 35th International Symposium on Computational Geometry, 2019

The Optimal Approximation Factor in Density Estimation.

[BibT_eX]

[DOI]

Olivier Bousquet

Daniel Kane

Proceedings of the Conference on Learning Theory, 2019

Private Center Points and Learning of Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

Generalized comparison trees for point-location problems.

[BibT_eX]

[DOI]

Daniel M. Kane

Shachar Lovett

Electron. Colloquium Comput. Complex., 2018

Are Two (Samples) Really Better Than One? On the Non-Asymptotic Performance of Empirical Revenue Maximization.

[BibT_eX]

[DOI]

Moshe Babaioff

Yannai A. Gonczarowski

Yishay Mansour

CoRR, 2018

A Sauer-Shelah-Perles Lemma for Sumsets.

[BibT_eX]

[DOI]

Zeev Dvir

Electron. J. Comb., 2018

Are Two (Samples) Really Better Than One?

[BibT_eX]

[DOI]

Moshe Babaioff

Yannai A. Gonczarowski

Yishay Mansour

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Learners that Use Little Information.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2018

2017

Active classification with comparison queries.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On Communication Complexity of Classification Problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Near-optimal linear decision trees for k-SUM and related problems.

[BibT_eX]

[DOI]

Daniel M. Kane

Shachar Lovett

Electron. Colloquium Comput. Complex., 2017

A learning problem that is independent of the set theory ZFC axioms.

[BibT_eX]

[DOI]

CoRR, 2017

Learners that Leak Little Information.

[BibT_eX]

[DOI]

CoRR, 2017

Twenty (simple) questions.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Submultiplicative Glivenko-Cantelli and Uniform Convergence of Revenues.

[BibT_eX]

[DOI]

Moshe Babaioff

Yannai A. Gonczarowski

Yishay Mansour

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

2016

Generalization and simplification in machine learning.

[BibT_eX]

[DOI]

PhD thesis, 2016

Sample Compression Schemes for VC Classes.

[BibT_eX]

[DOI]

J. ACM, 2016

Simple and optimal randomized fault-tolerant rumor spreading.

[BibT_eX]

[DOI]

Distributed Comput., 2016

On statistical learning via the lens of compression.

[BibT_eX]

[DOI]

Ofir David

CoRR, 2016

Supervised learning through the lens of compression.

[BibT_eX]

[DOI]

Ofir David

Proceedings of the Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, 2016

Hitting Set for Hypergraphs of Low VC-dimension.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Sign rank versus VC dimension.

[BibT_eX]

[DOI]

Proceedings of the 29th Conference on Learning Theory, 2016

Labeled Compression Schemes for Extremal Classes.

[BibT_eX]

[DOI]

Manfred K. Warmuth

Proceedings of the Algorithmic Learning Theory - 27th International Conference, 2016

2015

Proper PAC learning is compressing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Teaching and compressing for low VC-dimension.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Shattered Sets and the Hilbert Function.

[BibT_eX]

[DOI]

Cyrus Rashtchian

Electron. Colloquium Comput. Complex., 2015

Matchings vs hitting sets among half-spaces in low dimensional euclidean spaces.

[BibT_eX]

[DOI]

Rom Pinchasi

CoRR, 2015

Compressing and Teaching for Low VC-Dimension.

[BibT_eX]

[DOI]

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

Node-Balancing by Edge-Increments.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2015, 2015

2014

Fooling Pairs in Randomized Communication Complexity.

[BibT_eX]

[DOI]

Makrand Sinha

Electron. Colloquium Comput. Complex., 2014

Internal compression of protocols to entropy.

[BibT_eX]

[DOI]

Balthazar Bauer

Electron. Colloquium Comput. Complex., 2014

Sign rank, VC dimension and spectral gaps.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

A note on average-case sorting.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Direct Sum Fails for Zero Error Average Communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Shattering, Graph Orientations, and Connectivity.

[BibT_eX]

[DOI]

László Kozma

Electron. J. Comb., 2013

2012

Shattering-Extremal Systems

[BibT_eX]

[DOI]