Mark Sellke

According to our database, Mark Sellke authored at least 36 papers between 2017 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

On size-independent sample complexity of ReLU networks.

Mark Sellke

Inf. Process. Lett., 2024

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

Ryan Alweiss, Brice Huang, Mark Sellke

Electron. J. Comb., 2024

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

Tanishq Kumar, Kevin Luo, Mark Sellke

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.

Ahmed El Alaoui, Andrea Montanari, Mark Sellke

Random Struct. Algorithms, October, 2023

A Universal Law of Robustness via Isoperimetry.

Sébastien Bubeck, Mark Sellke

J. ACM, April, 2023

First-Order Bayesian Regret Analysis of Thompson Sampling.

Sébastien Bubeck, Mark Sellke

IEEE Trans. Inf. Theory, March, 2023

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

Mark Sellke, Aleksandrs Slivkins

Oper. Res., 2023

Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits.

Evelyn Xiao-Yue Gong, Mark Sellke

CoRR, 2023

Algorithmic Threshold for Multi-Species Spherical Spin Glasses.

Brice Huang, Mark Sellke

CoRR, 2023

Asymptotically Optimal Quantile Pure Exploration for Infinite-Armed Bandits.

Evelyn Xiao-Yue Gong, Mark Sellke

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.

Mark Sellke

Proceedings of the International Conference on Machine Learning, 2023

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting.

Ofer Grossman, Meghal Gupta, Mark Sellke

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

When Does Adaptivity Help for Quantum State Learning?

Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke

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

2022

Exact Minimum Number of Bits to Stabilize a Linear System.

Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke

IEEE Trans. Autom. Control., 2022

Tight Bounds for State Tomography with Incoherent Measurements.

Sitan Chen, Brice Huang, Jerry Li, Allen Liu, Mark Sellke

CoRR, 2022

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

Yining Chen, Elan Rosenfeld, Mark Sellke, Tengyu Ma, Andrej Risteski

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.

Brice Huang, Mark Sellke

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

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

Ahmed El Alaoui, Andrea Montanari, Mark Sellke

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.

Allen Liu, Mark Sellke

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

2021

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

Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke

IEEE Trans. Inf. Theory, 2021

Vertex Sparsification for Edge Connectivity.

Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, Mark Sellke, Daniel Vaz

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

Online Multiserver Convex Chasing and Optimization.

Sébastien Bubeck, Yuval Rabani, Mark Sellke

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

Metrical Service Systems with Transformations.

Sébastien Bubeck, Niv Buchbinder, Christian Coester, Mark Sellke

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.

Sébastien Bubeck, Thomas Budzinski, Mark Sellke

Proceedings of the Conference on Learning Theory, 2021

2020

Functions that Preserve Manhattan Distances.

Timothy Chu, Gary L. Miller, Shyam Narayanan, Mark Sellke

CoRR, 2020

Algorithmic pure states for the negative spherical perceptron.

Ahmed El Alaoui, Mark Sellke

CoRR, 2020

Sample Complexity of Incentivized Exploration.

Mark Sellke, Aleksandrs Slivkins

CoRR, 2020

Chasing Convex Bodies Optimally.

Mark Sellke

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

Chasing Nested Convex Bodies Nearly Optimally.

Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, Yuanzhi Li, Mark Sellke

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.

Sébastien Bubeck, Yuanzhi Li, Yuval Peres, Mark Sellke

Proceedings of the Conference on Learning Theory, 2020

2019

Vertex Sparsifiers for c-Edge Connectivity.

Yang P. Liu, Richard Peng, Mark Sellke

CoRR, 2019

First-Order Regret Analysis of Thompson Sampling.

Sébastien Bubeck, Mark Sellke

CoRR, 2019

Competitively chasing convex bodies.

Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke

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

2018

Chasing Nested Convex Bodies Nearly Optimally.

Sébastien Bubeck, Yin Tat Lee, Yuanzhi Li, Mark Sellke

CoRR, 2018

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

Victoria Kostina, Yuval Peres, Gireeja Ranade, Mark Sellke

CoRR, 2018

2017

Approximating Continuous Functions by ReLU Nets of Minimal Width.

Boris Hanin, Mark Sellke

CoRR, 2017