4 papers · 1 filter
Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to
Mathews Boban, Anqi Li, Shayan Oveis Gharan
We introduce a new family of trickledown theorems, a.k.a., local to global technique to bound the spectral gap of the Glauber dynamics for multi-state spin systems. In this techniq…
On Thin Perfect Matchings up to Polylogarithmic Factors
Alireza Haqi, Shayan Oveis Gharan
We resolve the thin matching problem proposed by Anari, Charikar and Ramakrishnan [ACR23] up to polylogarithmic factors. Given a fractional perfect matching , we say a perfect m…
High-Dimensional Expanders, the Sparsest Cut Problem, and Steurer's Conjecture
Farzam Ebrahimnejad, Shayan Oveis Gharan
In 2010, Steurer conjectured that any family of unit-norm vectors with polynomially small average correlation $\mathbb{E}_{i,j}|\langle v_i,v_j\rangle|\leq n^{-…
On approximability of the Permanent of PSD matrices
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
We study the complexity of approximating the permanent of a positive semidefinite matrix . 1. We design a new approximation algorithm for $\mathrm{per}…