3 papers
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 unit-norm vectors with polynomially small average correlation $\mathbb{E}_{i,j}|\langle v_i,v_j\rangle|\leq n^{-…
cs.DS2026
Optimal -Approximation of the Permanent of Positive Semidefinite Matrices
Nima Anari, Farzam Ebrahimnejad
We determine, up to lower-order terms in the exponent, the best possible deterministic polynomial-time approximation ratio for the permanent of a Hermitian positive semidefinite ma…
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 . 1. We design a new approximation algorithm for $\mathrm{per}…