Mark Sellke

See also Google Scholar or arXiv. Some videos below are by collaborators.


Mean square displacement of Brownian paths perturbed by bounded pair potentials
With Volker Betz and Tobias Schmidt

A Constructive Proof of the Spherical Parisi Formula
With Brice Huang

Sampling from Mean-Field Gibbs Measures via Diffusion Processes
With Ahmed El Alaoui and Andrea Montanari

Strong Topological Trivialization of Multi-Species Spherical Spin Glasses
With Brice Huang

Optimization Algorithms for Multi-Species Spherical Spin Glasses
With Brice Huang
Journal of Statistical Physics, accepted

Shattering in Pure Spherical Spin Glasses
With Ahmed El Alaoui and Andrea Montanari

The Threshold Energy of Low Temperature Langevin Dynamics for Pure Spherical Spin Glasses
arXiv Slides

Algorithmic Threshold for Multi-Species Spherical Spin Glasses
With Brice Huang
arXiv Video Slides

Almost Quartic Lower Bound for the Fröhlich Polaron's Effective Mass via Gaussian Domination
Duke Math Journal, accepted
arXiv Slides

Free Energy Subadditivity for Symmetric Random Hamiltonians
Journal of Mathematical Physics, Vol. 64 (2023) no. 4, 1-14
Journal arXiv

Sampling from the Sherrington-Kirkpatrick Gibbs measure via Algorithmic Stochastic Localization
With Ahmed El Alaoui and Andrea Montanari
FOCS 2022
Proceedings arXiv Slides

Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree
With Ahmed El Alaoui and Andrea Montanari
Random Structures & Algorithms, Vol. 63 (2023) no. 3, 689-715
Journal arXiv

Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
With Brice Huang
FOCS 2022
Proceedings arXiv Slides Short Video Long Video

Optimizing Mean-Field Spin Glasses with External Field
Electronic Journal of Probability, Vol. 29 (2024) no. 4, 1-47
Journal arXiv

Cutoff for the Asymmetric Riffle Shuffle
Annals of Probability, Vol. 50 (2022) no. 6, 2244-2287
Journal arXiv Slides

Algorithmic Pure States for the Negative Spherical Perceptron
With Ahmed El Alaoui
Journal of Statistical Physics, Vol 189 (2022) no. 27
Journal arXiv Slides Video

Approximate Ground States of Hypercube Spin Glasses are Near Corners
Comptes Rendus Mathématique, Vol. 359 (2021) no. 9, 1097-1105
Journal arXiv

Optimization of Mean-Field Spin Glasses
With Ahmed El Alaoui and Andrea Montanari
Annals of Probability, Vol. 49 (2021) no. 6, 2922-2960
Journal arXiv

Multi-Armed Bandits

Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits
With Xiao-Yue Gong
NeurIPS 2023
arXiv Slides Video Poster

Incentivizing Exploration with Linear Contexts and Combinatorial Actions
ICML 2023
Proceedings arXiv Slides

The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication
With Allen Liu
COLT 2022
Proceedings arXiv Long Slides Short Slides Video Twitter

Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
With Sébastien Bubeck and Thomas Budzinski
COLT 2021
Proceedings arXiv Slides Poster Twitter

The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
With Alex Slivkins
Operations Research, Vol. 71 (2023) no. 5, 1706-1732
Extended abstract in EC 2021
Journal Proceedings arXiv Slides Poster

Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without
With Sébastien Bubeck, Yuanzhi Li, and Yuval Peres
COLT 2020
Proceedings arXiv Video

First-Order Bayesian Regret Analysis of Thompson Sampling
With Sébastien Bubeck
IEEE Transactions on Information Theory, Vol. 69 (2023) no. 3, 1795-1823
Conference version in ALT 2020
Journal Proceedings arXiv Slides

Online Algorithms

Metrical Service Systems with Transformations
With Sébastien Bubeck, Niv Buchbinder, and Christian Coester
ITCS 2021
Proceedings arXiv Video

Online Multiserver Convex Chasing and Optimization
With Sébastien Bubeck and Yuval Rabani
SODA 2021
Proceedings arXiv

Chasing Convex Bodies Optimally
GAFA Seminar Notes, 2023
Conference version in SODA 2020. Awarded Best Paper and Best Student Paper.
Journal Proceedings arXiv Slides Long Video Short Video Blog post by Sébastien

Chasing Nested Convex Bodies Nearly Optimally
With Sébastien Bubeck, Bo'az Klartag, Yin Tat Lee, and Yuanzhi Li
SODA 2020
Proceedings arXiv Slides

Competitively Chasing Convex Bodies
With Sébastien Bubeck, Yin Tat Lee, and Yuanzhi Li
STOC 2019 and SIAM Journal on Computing Special Issue 52 (1), 67-81
Journal Proceedings arXiv Slides Long Video Short Video

Other Learning Theory

No Free Prune: Information-Theoretic Barriers to Pruning at Initialization
With Tanishq Kumar and Kevin Luo

On Size-Independent Sample Complexity of ReLU Networks
Information Processing Letters, accepted

When Does Adaptivity Help for Quantum State Learning?
With Sitan Chen, Brice Huang, Jerry Li, and Allen Liu
FOCS 2023
(Previously Tight Bounds for State Tomography with Incoherent Measurements, QIP 2023, merged with [CHLL22])
Proceedings arXiv Video

Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments
With Yining Chen, Elan Rosenfeld, Tengyu Ma, and Andrej Risteski
NeurIPS 2022
Proceedings arXiv Twitter

A Universal Law of Robustness via Isoperimetry
With Sébastien Bubeck
Journal of the ACM, Vol. 70 (2023) no. 2, Article 10, 1-18
Conference version in NeurIPS 2021. Awarded Outstanding Paper.
Journal Proceedings arXiv Slides Long Video Medium Video Short Video Poster Twitter
Featured in Quanta

Exact Minimum Number of Bits to Stabilize a Linear System
With Victoria Kostina, Yuval Peres, and Gireeja Ranade
IEEE Transactions on Automatic Control, Vol. 67 (2022) no. 10, 5548-5554
Conference version in IEEE Conference on Decision and Control 2018
Journal Proceedings arXiv

Stabilizing a System with an Unbounded Random Gain Using Only Finitely Many Bits
With Victoria Kostina, Yuval Peres, and Gireeja Ranade
IEEE Transactions on Information Theory,Vol. 67 (2021) no. 4, 2554-2561, Apr. 2021
Conference version in IEEE ISIT 2018
Journal Proceedings arXiv

Approximating Continuous Functions by ReLU Nets of Minimal Width
With Boris Hanin

Representations of Finite Groups

Tensor Quasi-Random Groups
Proceedings of the AMS, Series B, Vol. 9 (2022) no. 2, 12-21
Journal arXiv

Covering Irrep(Sn) With Tensor Products and Powers
Mathematische Annalen, Vol. 388 (2024), 831-865
Journal arXiv

The Saxl Conjecture for Fourth Powers via the Semigroup Property
With Sammy Luo
Journal of Algebraic Combinatorics, Vol. 45 (2017) no. 1, 33-80
Journal arXiv Slides

Biomedical Engineering

An Analytical, Mathematical Annuloplasty Ring Curvature Model for Planning of Valve-in-Ring Transcatheter Mitral Valve Replacement
With Matthew Park, Mateo Marin-Cuartas, Pearly Pandya, Yuanjia Zhu, Robert Wilkerson, David Holzhey, Michael Borger, and Y. Joseph Woo.
Journal of Thoracic and Cardiovascular Surgery (JTCVS) Techniques, Vol. 20 (August 2023), 45-54

A Novel Accelerated Fatigue Testing System for Pulsatile Applications of Cardiac Devices Using Widely Translatable Cam and Linkage-Based Mechanisms
With Matthew H. Park, Annabel M. Imbrie-Moore, Yuanjia Zhu, Mateo Marin-Cuartas, Robert Wilkerson, and Y. Joseph Woo
Medical Engineering & Physics, Vol. 109 (2022), 103896

Biomimetic Six-Axis Robots Replicate Human Cardiac Papillary Muscle Motion: Pioneering the Next Generation of Biomechanical Heart Simulator Technology
With Annabel Imbrie-Moore, Matthew Park, Michael Paulsen, Rohun Kulkami, Hanjay Wang, Yuanjia Zhu, Justin Farry, Alexandra Bourdillon, Christine Callinan, Haley Lucian, Camille Hironaka, Daniela Deschamps and Y. Joseph Woo
Journal of the Royal Society Interface, Vol. 17 (2020), Issue 173


Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
With Ofer Grossman and Meghal Gupta
FOCS 2023
Proceedings arXiv

Improved Lower Bound for Frankl's Union-Closed Sets Conjecture
With Ryan Alweiss and Brice Huang

Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
With Josh Alman, Timothy Chu, Gary Miller, Shyam Narayanan, and Zhao Song
arXiv Video

Vertex Sparsification for Edge Connectivity
With Parinya Chalermsook, Syamantak Das, Yunbum Kook, Bundit Laekhanukit, Yang P. Liu, Richard Peng, and Daniel Vaz
(Merge and extension of [LPS19] and [CDLZ19])
SODA 2021
Proceedings arXiv Video

On the Number of 2-protected Nodes in Tries and Suffix Trees
With Jeffrey Gaither, Yushi Homma, and Mark Daniel Ward
Discrete Mathematics and Theoretical Computer Science, Vol. AQ (2012), 381-398

PhD Thesis

High-Dimensional Problems in Probability, Optimization, and Learning
pdf official