Noah Golowich

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Exploration is harder than prediction: cryptographically separating reinforcement learning from supervised learning	2026-06-23	Paper
Smooth Nash equilibria: algorithms and complexity	2025-11-04	Paper
Near-tight closure bounds for the Littlestone and threshold dimensions	2025-02-11	Paper
Planning and learning in partially observable systems via filter stability	2024-05-08	Paper
Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
Fast rates for nonparametric online learning: from realizability to learning in games Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing	2023-12-08	Paper
Sample-efficient proper PAC learning with approximate differential privacy Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
Pure differentially private summation from anonymous messages (available as arXiv preprint)	2023-11-02	Paper
On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy	2021-12-08	Paper
Size-independent sample complexity of neural networks Information and Inference: A Journal of the IMA	2021-08-16	Paper
Round Complexity of Common Randomness Generation: The Amortized Setting Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Near-tight closure bounds for Littlestone and threshold dimensions	2020-07-07	Paper
Communication-rounds tradeoffs for common randomness and secret key generation Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms	2019-10-15	Paper
Coloring chains for compression with uncertain priors The Electronic Journal of Combinatorics	2019-03-05	Paper
Coloring chains for compression with uncertain priors The Electronic Journal of Combinatorics	2019-03-05	Paper
The \(m\)-degenerate chromatic number of a digraph Discrete Mathematics	2016-04-08	Paper
Acyclic subgraphs of planar digraphs The Electronic Journal of Combinatorics	2015-08-27	Paper
Acyclic subgraphs of planar digraphs The Electronic Journal of Combinatorics	2015-08-27	Paper
Degree of regularity of linear homogeneous equations and inequalities Journal of Combinatorics	2014-12-10	Paper
Resolving a conjecture on degree of regularity of linear homogeneous equations The Electronic Journal of Combinatorics	2014-09-09	Paper
Resolving a conjecture on degree of regularity of linear homogeneous equations The Electronic Journal of Combinatorics	2014-09-09	Paper

Research outcomes over time

This page was built for person: Noah Golowich