4 papers · 1 filter
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…