Mark Sellke


Research

See also my Google Scholar page. Videos below are by myself or collaborators.

Probability

Optimizing Mean-Field Spin Glasses with External Field
arXiv

Cutoff for the Asymmetric Riffle Shuffle
arXiv

Algorithmic Pure States for the Negative Spherical Perceptron
With Ahmed El Alaoui.
arXiv Slides Video

Approximate Ground States of Hypercube Spin Glasses are Near Corners
Comptes Rendus, to appear
arXiv

Optimization of Mean-Field Spin Glasses
With Ahmed El Alaoui and Andrea Montanari.
Annals of Probability, to appear
arXiv Video

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 Video

Chasing Convex Bodies Optimally
SODA 2020. Best paper and best student paper.
Proceedings arXiv Slides Short Video Long 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. Invited to the SICOMP special issue.
Proceedings arXiv Slides Short Video Long Video

Multi-Armed Bandits

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 Video

The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
With Alex Slivkins.
EC 2021
Proceedings arXiv Slides

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.
ALT 2020
Proceedings arXiv Slides

Offline Machine Learning

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

A Universal Law of Robustness via Isoperimetry
With Sébastien Bubeck.
arXiv

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

Group Representation Theory

Tensor Quasi-Random Groups
Proceedings of the AMS, to appear
arXiv

Covering Irrep(Sn) With Tensor Products and Powers
arXiv

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

Control Theory

Exact Minimum Number of Bits to Stabilize a Linear System
With Victoria Kostina, Yuval Peres, and Gireeja Ranade.
IEEE CDC 2018
Proceedings arXiv Video

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, no. 4, pp. 2554-2561, Apr. 2021.
Preliminary version in IEEE ISIT 2018
Journal Proceedings arXiv

Miscellaneous

Functions that Preserve Manhattan Distances
With Timothy Chu, Gary Miller, and Shyam Narayanan.
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 this paper and this paper)
SODA 2021
Proceedings arXiv Video

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

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, volume AQ (2012), 381-398
Journal