Farzam Ebrahimnejad

activity

20162026

collaborators

8 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 $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…

math.CO2021

Non-existence of annular separators in geometric graphs

Farzam Ebrahimnejad, James R. Lee

Benjamini and Papasoglou (2011) showed that planar graphs with uniform polynomial volume growth admit $1$ -dimensional annular separators: The vertices at graph distance $R$ from an…

cs.DS2021

Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan

We show that the ratio of the number of near perfect matchings to the number of perfect matchings in $d$ -regular strong expander (non-bipartite) graphs, with $2 n$ vertices, is a po…

math.PR2020

On planar graphs of uniform polynomial growth

Farzam Ebrahimnejad, James R. Lee

Consider an infinite planar graph with uniform polynomial growth of degree d > 2. Many examples of such graphs exhibit similar geometric and spectral properties, and it has been co…

cs.FL2016

On the Gap Between Separating Words and Separating Their Reversals

Farzam Ebrahimnejad

A deterministic finite automaton (DFA) separates two strings $w$ and $x$ if it accepts $w$ and rejects $x$ . The minimum number of states required for a DFA to separate $w$ and $x$ …

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

Optimal e(γ+o(1))n-Approximation of the Permanent of Positive Semidefinite Matrices

On approximability of the Permanent of PSD matrices

Multiscale entropic regularization for MTS on general metric spaces

Non-existence of annular separators in geometric graphs

Counting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs

On planar graphs of uniform polynomial growth

On the Gap Between Separating Words and Separating Their Reversals

Optimal $e^{(γ + o (1)) n}$ -Approximation of the Permanent of Positive Semidefinite Matrices