9 papers
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…
A Simple Algorithm for Best Separable State
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman
We study the best separable state problem (BSS), which asks for the maximum acceptance probability of a quantum measurement over unentangled states. In classical terms, the goal is…
Markov Chains Approximate Message Passing
Amit Rajaraman, David X. Wu
Markov chain Monte Carlo algorithms have long been observed to obtain near-optimal performance in various Bayesian inference settings. However, developing a supporting theory that…
Faster MAX-CUT on Bounded Threshold Rank Graphs
Prashanti Anderson, Samuel B. Hopkins, Amit Rajaraman +1
We design new algorithms for approximating 2CSPs on graphs with bounded threshold rank, that is, whose normalized adjacency matrix has few eigenvalues larger than , sm…
Eigenvalue Bounds for Random Matrices via Zerofreeness
Sidhanth Mohanty, Amit Rajaraman
We introduce a new technique to prove bounds for the spectral radius of a random matrix, based on using Jensen's formula to establish the zerofreeness of the associated characteris…
The Fundamental Limits of Recovering Planted Subgraphs
Daniel Lee, Francisco Pernice, Amit Rajaraman +1
Given an arbitrary subgraph and , the planted subgraph model is defined as follows. A statistician observes the union a random copy of , together…
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…
Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
Kuikui Liu, Sidhanth Mohanty, Prasad Raghavendra +2
Many natural Markov chains fail to mix to their stationary distribution in polynomially many steps. Often, this slow mixing is inevitable since it is computationally intractable to…
Fast Mixing in Sparse Random Ising Models
Kuikui Liu, Sidhanth Mohanty, Amit Rajaraman +1
Motivated by the community detection problem in Bayesian inference, as well as the recent explosion of interest in spin glasses from statistical physics, we study the classical Gla…