13 citations · 42 across the 23 of their papers we have counts for
14 papers · 1 filter
Sampling from the Sherrington-Kirkpatrick Model up to Criticality
Hang Du, Brice Huang, Sidhanth Mohanty +1
We prove that the simulated annealing algorithm efficiently samples from the Sherrington-Kirkpatrick model at inverse temperature to an arbitrary inverse polynomial accuracy…
Algorithmic threshold for high-dimensional projection pursuit I: general theory
Brice Huang, Mark Sellke, Nike Sun
We study a null model of high-dimensional projection pursuit: we are given points sampled i.i.d. from a standard gaussian in dimensions, where with $M/N\toα\…
Overlap distribution of the critical Sherrington-Kirkpatrick model
Hang Du, Brice Huang
We study the distribution of the two-replica overlap in the Ising and spherical Sherrington-Kirkpatrick models at the critical inverse temperature . Our main result…
Fluctuations of the Sherrington-Kirkpatrick free energy at critical temperature
Hang Du, Brice Huang
We consider the Sherrington-Kirkpatrick spin glass model at the critical inverse temperature with zero external field. We prove that the free energy of thi…
Weak Poincaré Inequalities, Simulated Annealing, and Sampling from Spherical Spin Glasses
Brice Huang, Sidhanth Mohanty, Amit Rajaraman +1
There has been a recent surge of powerful tools to show rapid mixing of Markov chains, via functional inequalities such as Poincaré inequalities. In many situations, Markov chains…
Sampling from Spherical Spin Glasses in Total Variation via Algorithmic Stochastic Localization
Brice Huang, Andrea Montanari, Huy Tuan Pham
We consider the problem of algorithmically sampling from the Gibbs measure of a mixed -spin spherical spin glass. We give a polynomial-time algorithm that samples from the Gibbs…
Capacity threshold for the Ising perceptron
Brice Huang
We show that the capacity of the Ising perceptron is with high probability upper bounded by the constant conjectured by Krauth and Mézard, under the conditi…
A Constructive Proof of the Spherical Parisi Formula
Brice Huang, Mark Sellke
The Parisi formula for the free energy is among the crown jewels in the theory of spin glasses. We present a simpler proof of the lower bound in the case of the spherical mean-fiel…
Strong Topological Trivialization of Multi-Species Spherical Spin Glasses
Brice Huang, Mark Sellke
We study the landscapes of multi-species spherical spin glasses. Our results determine the phase boundary for annealed trivialization of the number of critical points, and establis…
Optimization Algorithms for Multi-Species Spherical Spin Glasses
Brice Huang, Mark Sellke
This paper develops approximate message passing algorithms to optimize multi-species spherical spin glasses. We first show how to efficiently achieve the algorithmic threshold ener…
Algorithmic Threshold for Multi-Species Spherical Spin Glasses
Brice Huang, Mark Sellke
We study efficient optimization of the Hamiltonians of multi-species spherical spin glasses. Our results characterize the maximum value attained by algorithms that are suitably Lip…
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…
De Finetti-Style Results for Wishart Matrices: Combinatorial Structure and Phase Transitions
Matthew Brennan, Guy Bresler, Brice Huang
A recent line of work has studied the relationship between the Wishart matrix , where has i.i.d. standard Gaussian entries, and the correspo…
Convergence of Maximum Bisection Ratio of Sparse Random Graphs
Brice Huang
We consider sequences of large sparse random graphs whose degree distribution approaches a limit with finite mean. This model includes both the random regular graphs and the Erdös-…