130 citations · 209 across the 59 of their papers we have counts for
7 papers · 1 filter
Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree
Ahmed El Alaoui, Andrea Montanari, Mark Sellke
Given a graph of degree over vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth ,…
Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses
Brice Huang, Mark Sellke
We study the problem of algorithmically optimizing the Hamiltonian of a spherical or Ising mixed -spin glass. The maximum asymptotic value of is cha…
Iterative Feature Matching: Toward Provable Domain Generalization with Logarithmic Environments
Yining Chen, Elan Rosenfeld, Mark Sellke +2
Domain generalization aims at performing well on unseen test environments with data from a limited number of training environments. Despite a proliferation of proposal algorithms f…
A Universal Law of Robustness via Isoperimetry
Sébastien Bubeck, Mark Sellke
Classically, data interpolation with a parametrized model class is possible as long as the number of parameters is larger than the number of equations to be satisfied. A puzzling p…
Optimizing Mean Field Spin Glasses with External Field
Mark Sellke
We consider the Hamiltonians of mean-field spin glasses, which are certain random functions defined on high-dimensional cubes or spheres in . The asymptotic maxi…
Tensor Quasi-Random Groups
Mark Sellke
Gowers has elegantly characterized the finite groups in which for any positive density subsets . This property, quasi-randomness, holds if and only…
Cutoff for the Asymmetric Riffle Shuffle
Mark Sellke
In the Gilbert-Shannon-Reeds shuffle, a deck of cards is cut into two approximately equal parts which are then riffled uniformly at random. Bayer and Diaconis famously showed t…