Shayan Oveis Gharan

activity

20242026

collaborators

7 papers

cs.DS2026

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β \leq \frac{1}{2} + ε$

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…

cs.DS2026

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 $x$ , we say a perfect m…

cs.DS2026

High-Dimensional Expanders, the Sparsest Cut Problem, and Steurer's Conjecture

Farzam Ebrahimnejad, Shayan Oveis Gharan

In 2010, Steurer conjectured that any family of $n$ unit-norm vectors $v_{1}, \dots, v_{n}$ with polynomially small average correlation $\mathbb{E}_{i,j}|\langle v_i,v_j\rangle|\leq n^{-…

math.CO2025

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition

Jonathan Leake, Shayan Oveis Gharan

Let $μ$ be a probability distribution on a multi-state spin system on a set $V$ of sites; equivalently, a $d$ -partite simplicial complex with distribution $μ$ on maximal faces. For…

math.CO2025

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences

Jonathan Leake, Kasper Lindberg, Shayan Oveis Gharan

Let $X$ be a $d$ -partite $d$ -dimensional simplicial complex with parts $T_{1}, \dots, T_{d}$ and let $μ$ be a distribution on the facets of $X$ . Informally, we say $(X, μ)$ is a path comp…

math.CO2025

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs

Shayan Oveis Gharan, Arvin Sahami

For a linear code $C \subseteq F_{2}^{n}$ and $α \in [0, 1]$ , call a set $S \subseteq [n]$ an (unweighted) one-sided $α$ -sparsifier of $C$ if for all $c \in…

cs.DS2024

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 $A \in C^{n \times n}$ . 1. We design a new approximation algorithm for $\mathrm{per}…

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to β≤21​+ε

On Thin Perfect Matchings up to Polylogarithmic Factors

High-Dimensional Expanders, the Sparsest Cut Problem, and Steurer's Conjecture

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs

On approximability of the Permanent of PSD matrices

Rank-1-perturbed trickledown theorems: Mixing time of Glauber dynamics for the Sherrington-Kirkpatrick model up to $β \leq \frac{1}{2} + ε$