88 citations · 152 across the 20 of their papers we have counts for
21 papers
Universality and sharp thresholds for ellipsoid fitting
Frederic Koehler, Youngtak Sohn
We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a co…
Low-degree estimation thresholds in planted hypergraphs and tensor PCA
Daniel Fu, Youngtak Sohn
A central question in high-dimensional statistics is to understand statistical--computational gaps: regimes in which recovering a hidden signal is information-theoretically possibl…
Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
Dan Mikulincer, Youngtak Sohn
We study the mixing time of Glauber dynamics for Ising models in which the interaction matrix contains a single negative spectral outlier. This class includes the anti-ferromagneti…
Balanced multi-species spin glasses
Erik Bates, Youngtak Sohn
We identify a special class of multi-species spin glass models: ones in which the species proportions serve to ''balance'' out the interaction strengths. For this class, we prove a…
Rapid phase ordering for Ising and Potts dynamics on random regular graphs
Reza Gheissari, Allan Sly, Youngtak Sohn
We consider the Ising, and more generally, -state Potts Glauber dynamics on random -regular graphs on vertices at low temperatures . The mixing…
Stochastic block models with many communities and the Kesten--Stigum bound
Byron Chin, Elchanan Mossel, Youngtak Sohn +1
We study the inference of communities in stochastic block models with a growing number of communities. For block models with vertices and a fixed number of communities , it…
Sharp Phase Transitions in Estimation with Low-Degree Polynomials
Youngtak Sohn, Alexander S. Wein
High-dimensional planted problems, such as finding a hidden dense subgraph within a random graph, often exhibit a gap between statistical and computational feasibility. While recov…
Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
Elchanan Mossel, Allan Sly, Youngtak Sohn
The stochastic block model is a canonical model of communities in random graphs. It was introduced in the social sciences and statistics as a model of communities, and in theoretic…
Parisi formula for balanced Potts spin glass
Erik Bates, Youngtak Sohn
The Potts spin glass is a generalization of the Sherrington--Kirkpatrick (SK) model that allows for spins to take more than two values. Based on a novel synchronization mechanism,…
Universality of max-margin classifiers
Andrea Montanari, Feng Ruan, Basil Saeed +1
Maximum margin binary classification is one of the most fundamental algorithms in machine learning, yet the role of featurization maps and the high-dimensional asymptotics of the m…
Upper bounds on the -colorability threshold of random -regular -uniform hypergraphs for
Evan Chang, Neel Kolhe, Youngtak Sohn
For a large class of random constraint satisfaction problems (CSP), deep but non-rigorous theory from statistical physics predict the location of the sharp satisfiability transitio…
Local geometry of NAE-SAT solutions in the condensation regime
Allan Sly, Youngtak Sohn
The local behavior of typical solutions of random constraint satisfaction problems (CSP) describes many important phenomena including clustering thresholds, decay of correlations,…
Sharp thresholds in inference of planted subgraphs
Elchanan Mossel, Jonathan Niles-Weed, Youngtak Sohn +2
A major question in the study of the Erdős--Rényi random graph is to understand the probability that it contains a given subgraph. This study originated in classical work of Erdős…
Exact Phase Transitions for Stochastic Block Models and Reconstruction on Trees
Elchanan Mossel, Allan Sly, Youngtak Sohn
In this paper we continue to rigorously establish the predictions in ground breaking work in statistical physics by Decelle, Krzakala, Moore, Zdeborová (2011) regarding the block m…
Agreement and Statistical Efficiency in Bayesian Perception Models
Yash Deshpande, Elchanan Mossel, Youngtak Sohn
Bayesian models of group learning are studied in Economics since the 1970s. and more recently in computational linguistics. The models from Economics postulate that agents maximize…
One-step replica symmetry breaking of random regular NAE-SAT II
Danny Nam, Allan Sly, Youngtak Sohn
Continuing our earlier work in \cite{nss20a}, we study the random regular k-NAE-SAT model in the condensation regime. In \cite{nss20a}, the 1RSB properties of the model were establ…
Crisanti-Sommers formula and simultaneous symmetry breaking in multi-species spherical spin glasses
Erik Bates, Youngtak Sohn
There is a rich history of expressing the limiting free energy of mean-field spin glasses as a variational formula over probability measures on , where the measure represent…
Free energy in multi-species mixed -spin spherical models
Erik Bates, Youngtak Sohn
We prove a Parisi formula for the limiting free energy of multi-species spherical spin glasses with mixed -spin interactions. The upper bound involves a Guerra-style interpolati…
One-step replica symmetry breaking of random regular NAE-SAT I
Danny Nam, Allan Sly, Youngtak Sohn
In a broad class of sparse random constraint satisfaction problems(CSP), deep heuristics from statistical physics predict that there is a condensation phase transition before the s…
The generalization error of max-margin linear classifiers: Benign overfitting and high dimensional asymptotics in the overparametrized regime
Andrea Montanari, Feng Ruan, Youngtak Sohn +1
Modern machine learning classifiers often exhibit vanishing classification error on the training set. They achieve this by learning nonlinear representations of the inputs that map…
Replica symmetry breaking in multi-species Sherrington-Kirkpatrick model
Erik Bates, Leila Sloman, Youngtak Sohn
In the Sherrington-Kirkpatrick (SK) and related mixed -spin models, there is interest in understanding replica symmetry breaking at low temperatures. For this reason, the so-cal…