Mark Sellke

CoRR, June, 2025

Strong Low Degree Hardness for the Number Partitioning Problem.

[BibT_eX]

[DOI]

Rushil Mallarapu

CoRR, May, 2025

Tight Low Degree Hardness for Optimizing Pure Spherical Spin Glasses.

[BibT_eX]

[DOI]

CoRR, April, 2025

Strong Low Degree Hardness for Stable Local Optima in Spin Glasses.

[BibT_eX]

[DOI]

CoRR, January, 2025

2024

On size-independent sample complexity of ReLU networks.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2024

Improved Lower Bound for Frankl's Union-Closed Sets Conjecture.

[BibT_eX]

[DOI]

Ryan Alweiss

Electron. J. Comb., 2024

Metric Transforms and Low Rank Representations of Kernels for Fast Attention.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 38: Annual Conference on Neural Information Processing Systems 2024, 2024

No Free Prune: Information-Theoretic Barriers to Pruning at Initialization.

[BibT_eX]

[DOI]

Tanishq Kumar

Kevin Luo

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree.

[BibT_eX]

[DOI]

Ahmed El Alaoui

Andrea Montanari

Random Struct. Algorithms, October, 2023

Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits.

[BibT_eX]

[DOI]

Evelyn Xiao-Yue Gong

CoRR, 2023

Algorithmic Threshold for Multi-Species Spherical Spin Glasses.

[BibT_eX]

[DOI]

CoRR, 2023

Asymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits.

[BibT_eX]

[DOI]

Evelyn Xiao-Yue Gong

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

Incentivizing Exploration with Linear Contexts and Combinatorial Actions.

[BibT_eX]

[DOI]

Proceedings of the International Conference on Machine Learning, 2023

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting.

[BibT_eX]

[DOI]

Ofer Grossman

Meghal Gupta

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

When Does Adaptivity Help for Quantum State Learning?

[BibT_eX]

[DOI]

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

2022

Tight Bounds for State Tomography with Incoherent Measurements.

[BibT_eX]

[DOI]

CoRR, 2022

Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments.

[BibT_eX]

[DOI]

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

Tight Lipschitz Hardness for optimizing Mean Field Spin Glasses.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Sampling from the Sherrington-Kirkpatrick Gibbs measure via algorithmic stochastic localization.

[BibT_eX]

[DOI]

Ahmed El Alaoui

Andrea Montanari

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication.

[BibT_eX]

[DOI]

Allen Liu

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

2021

Vertex Sparsification for Edge Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Online Multiserver Convex Chasing and Optimization.

[BibT_eX]

[DOI]

Yuval Rabani

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity.

[BibT_eX]

[DOI]

Aleksandrs Slivkins

Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

A Universal Law of Robustness via Isoperimetry.

[BibT_eX]

[DOI]

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

Metrical Service Systems with Transformations.

[BibT_eX]

[DOI]

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

Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions.

[BibT_eX]

[DOI]

Thomas Budzinski

Proceedings of the Conference on Learning Theory, 2021

2020

Functions that Preserve Manhattan Distances.

[BibT_eX]

[DOI]

CoRR, 2020

Algorithmic pure states for the negative spherical perceptron.

[BibT_eX]

[DOI]

Ahmed El Alaoui

CoRR, 2020

Sample Complexity of Incentivized Exploration.

[BibT_eX]

[DOI]

Aleksandrs Slivkins

CoRR, 2020

Chasing Convex Bodies Optimally.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Chasing Nested Convex Bodies Nearly Optimally.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2020

First-Order Bayesian Regret Analysis of Thompson Sampling.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Learning Theory, 2020

2019

Vertex Sparsifiers for c-Edge Connectivity.

[BibT_eX]

[DOI]

Yang P. Liu

Richard Peng

CoRR, 2019

First-Order Regret Analysis of Thompson Sampling.

[BibT_eX]

[DOI]

CoRR, 2019

Competitively chasing convex bodies.

[BibT_eX]

[DOI]

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

2018

Chasing Nested Convex Bodies Nearly Optimally.

[BibT_eX]

[DOI]

CoRR, 2018

Stabilizing a system with an unbounded random gain using only a finite number of bits.

[BibT_eX]

[DOI]

CoRR, 2018

Stabilizing a System with an Unbounded Random Gain Using Only Finitely Many Bits.

[BibT_eX]

[DOI]

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Exact minimum number of bits to stabilize a linear system.

[BibT_eX]

[DOI]

Proceedings of the 57th IEEE Conference on Decision and Control, 2018

2017

Approximating Continuous Functions by ReLU Nets of Minimal Width.

[BibT_eX]

[DOI]

Boris Hanin