Farzam Ebrahimnejad

activity

20162026

collaborators

Showing cs.DSShow all

5 papers · 1 filter

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^{-…

cs.DS2026

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

cs.DS2021

Multiscale entropic regularization for MTS on general metric spaces

Farzam Ebrahimnejad, James R. Lee

We present an $O ((lo g n)^{2})$ -competitive algorithm for metrical task systems (MTS) on any $n$ -point metric space that is also $1$ -competitive for service costs. This matches the c…