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 2021Show all

4 papers · 1 filter

cs.DS2021

Stochastic Vertex Cover with Few Queries

Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan

We study the minimum vertex cover problem in the following stochastic setting. Let $G$ be an arbitrary given graph, $p \in (0, 1]$ a parameter of the problem, and let $G_{p}$ be a ra…

cs.DS2021

Improved Analysis of EDCS via Gallai-Edmonds Decomposition

Soheil Behnezhad

In this note, we revisit the edge-degree constrained subgraph (EDCS) introduced by Bernstein and Stein (ICALP'15). An EDCS is a sparse subgraph satisfying simple edge-degree constr…

cs.DS2021

Time-Optimal Sublinear Algorithms for Matching and Vertex Cover

Soheil Behnezhad

We study the problem of estimating the size of maximum matching and minimum vertex cover in sublinear time. Denoting the number of vertices by $n$ and the average degree in the gra…

cs.DS2021

Beating Two-Thirds For Random-Order Streaming Matching

Sepehr Assadi, Soheil Behnezhad

We study the maximum matching problem in the random-order semi-streaming setting. In this problem, the edges of an arbitrary $n$ -vertex graph $G = (V, E)$ arrive in a stream one by o…