4 citations · 10 across the 10 of their papers we have counts for
18 papers
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic…
Almost 3-Approximate Correlation Clustering in Constant Rounds
Soheil Behnezhad, Moses Charikar, Weiyun Ma +1
We study parallel algorithms for correlation clustering. Each pair among objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbit…
New Trade-Offs for Fully Dynamic Matching via Hierarchical EDCS
Soheil Behnezhad, Sanjeev Khanna
We study the maximum matching problem in fully dynamic graphs: a graph is undergoing both edge insertions and deletions, and the goal is to efficiently maintain a large matching af…
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…
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 -vertex graph arrive in a stream one by o…
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…