Shayan Oveis Gharan

activity

20242026

collaborators

6 papers

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.CO2026

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

Jonathan Leake, Shayan Oveis Gharan

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

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 $I^¼$ be a distribution on the facets of $X$ . Informally, we say $(X, I^¼)$ is a path co…

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 $I^\pm \in [0, 1]$ , call a set $S \subseteq [n]$ an (unweighted) one-sided $I^\pm$ -sparsifier of $C$ if for all $c \i…

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}…