Soheil Behnezhad

activity

20162026

most citedMassively Parallel Symmetry Breaking on Sparse Graphs: MIS and Maximal Matching

12 citations · 29 across the 37 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.DC2020★ 2 cited

Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice

Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +3

We study fundamental graph problems such as graph connectivity, minimum spanning forest (MSF), and approximate maximum (weight) matching in a distributed setting. In particular, we…

cs.DS2020★ 2 cited

Stochastic Weighted Matching: $(1 - ε)$ Approximation

Soheil Behnezhad, Mahsa Derakhshan

Let $G = (V, E)$ be a given edge-weighted graph and let its {\em realization} $G$ be a random subgraph of $G$ that includes each edge $e \in E$ independently with probabili…

cs.DS2020

Stochastic Matching with Few Queries: $(1 - ε)$ Approximation

Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi

Suppose that we are given an arbitrary graph $G = (V, E)$ and know that each edge in $E$ is going to be realized independently with some probability $p$ . The goal in the stochastic m…

Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice

Stochastic Weighted Matching: (1−ε) Approximation

Stochastic Matching with Few Queries: (1−ε) Approximation

Stochastic Weighted Matching: $(1 - ε)$ Approximation

Stochastic Matching with Few Queries: $(1 - ε)$ Approximation