| Publication | Date of Publication | Type |
|---|
Optimal prediction using expert advice and randomized Littlestone dimension
SIAM Journal on Computing | 2025-10-24 | Paper |
Diagonalization Games
American Mathematical Monthly | 2024-12-12 | Paper |
Boosting simple learners
TheoretiCS | 2024-07-03 | Paper |
scientific article; zbMATH DE number 7829291 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
Learnability can be independent of set theory (invited paper)
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
A theory of universal learning
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Boosting simple learners
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Adversarial laws of large numbers and optimal regret in online classification
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Adversarial laws of large numbers and optimal regret in online classification
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Private and Online Learnability Are Equivalent
Journal of the ACM | 2023-04-27 | Paper |
| Replicability and stability in learning | 2023-04-07 | Paper |
| Diagonalization Games | 2023-01-05 | Paper |
On the perceptron's compression
(available as arXiv preprint) | 2022-12-16 | Paper |
| The unstable formula theorem revisited via algorithms | 2022-12-09 | Paper |
| scientific article; zbMATH DE number 7561527 (Why is no real title available?) | 2022-07-21 | Paper |
| On weak \(\varepsilon\)-nets and the Radon number | 2022-07-18 | Paper |
Unlabeled sample compression schemes and corner peelings for ample and maximum classes
Journal of Computer and System Sciences | 2022-04-04 | Paper |
Unlabeled sample compression schemes and corner peelings for ample and maximum classes
Journal of Computer and System Sciences | 2022-04-04 | Paper |
| How Expressive Are Friendly School Partitions? | 2022-03-21 | Paper |
Elementary derivations of the Euclidean Hurwitz algebras: adapted from Gadi Moran's last paper
The American Mathematical Monthly | 2021-09-27 | Paper |
| Agnostic Online Learning and Excellent Sets | 2021-08-12 | Paper |
Generalized comparison trees for point-location problems
(available as arXiv preprint) | 2021-07-28 | Paper |
On weak \(\epsilon\)-nets and the Radon number
Discrete & Computational Geometry | 2021-01-29 | Paper |
A Sauer-Shelah-Perles lemma for lattices
The Electronic Journal of Combinatorics | 2020-11-05 | Paper |
Private PAC learning implies finite Littlestone dimension
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Near-optimal linear decision trees for \(k\)-SUM and related problems
Journal of the ACM | 2019-11-21 | Paper |
Twenty (short) questions
Combinatorica | 2019-09-04 | Paper |
Near-optimal linear decision trees for k-SUM and related problems
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Approximate nonnegative rank is equivalent to the smooth rectangle bound
Computational Complexity | 2019-06-20 | Paper |
| The Optimal Approximation Factor in Density Estimation | 2019-02-10 | Paper |
| Learners that use little information | 2019-02-06 | Paper |
Learners that use little information
(available as arXiv preprint) | 2019-02-06 | Paper |
A Sauer-Shelah-Perles lemma for sumsets
The Electronic Journal of Combinatorics | 2018-11-22 | Paper |
A Sauer-Shelah-Perles lemma for sumsets
The Electronic Journal of Combinatorics | 2018-11-22 | Paper |
| The entropy of lies: playing twenty questions with a liar | 2018-11-06 | Paper |
Sample Compression Schemes for VC Classes
Journal of the ACM | 2018-08-02 | Paper |
Sign rank versus Vapnik-Chervonenkis dimension
Sbornik: Mathematics | 2018-04-06 | Paper |
Shattered sets and the Hilbert function
(available as arXiv preprint) | 2018-03-21 | Paper |
Hitting Set for hypergraphs of low VC-dimension
(available as arXiv preprint) | 2018-03-02 | Paper |
Teaching and Compressing for Low VC-Dimension
A Journey Through Discrete Mathematics | 2018-02-26 | Paper |
| Internal Compression of Protocols to Entropy | 2017-08-31 | Paper |
Twenty (simple) questions
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Direct sum fails for zero error average communication
Proceedings of the 5th conference on Innovations in theoretical computer science | 2017-05-19 | Paper |
Fooling pairs in randomized communication complexity
Structural Information and Communication Complexity | 2016-12-01 | Paper |
Direct sum fails for zero-error average communication
Algorithmica | 2016-11-29 | Paper |
Labeled compression schemes for extremal classes
Lecture Notes in Computer Science | 2016-11-09 | Paper |
| On statistical learning via the lens of compression | 2016-10-11 | Paper |
Simple and optimal randomized fault-tolerant rumor spreading
Distributed Computing | 2016-05-23 | Paper |
A note on average-case sorting
Order | 2016-03-02 | Paper |
Node-balancing by edge-increments
Algorithms - ESA 2015 | 2015-11-19 | Paper |
| Matchings vs hitting sets among half-spaces in low dimensional euclidean spaces | 2015-07-09 | Paper |
Sign rank versus VC dimension
(available as arXiv preprint) | 2015-03-26 | Paper |
Shattering, graph orientations, and connectivity
The Electronic Journal of Combinatorics | 2014-08-14 | Paper |
Shattering, graph orientations, and connectivity
The Electronic Journal of Combinatorics | 2014-08-14 | Paper |
Approximate nonnegative rank is equivalent to the smooth rectangle bound
Automata, Languages, and Programming | 2014-07-01 | Paper |
| Shattering-Extremal Systems | 2012-11-13 | Paper |
