12 citations · 29 across the 37 of their papers we have counts for
9 papers · 1 filter
Stochastic Matching via In-n-Out Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, Alma Ghafari +1
Consider the following stochastic matching problem. Given a graph , an unknown subgraph is realized where includes every edge of independently…
Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim
Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include vertex coloring, maximal…
Vizing's Theorem in Near-Linear Time
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3
Vizing's theorem states that any -vertex -edge graph of maximum degree can be edge colored using at most different colors [Vizing, 1964]. Vizing's original proof i…
Massively Parallel Minimum Spanning Tree in General Metric Spaces
Amir Azarmehr, Soheil Behnezhad, Rajesh Jayaram +3
We study the minimum spanning tree (MST) problem in the massively parallel computation (MPC) model. Our focus is particularly on the *strictly sublinear* regime of MPC where the sp…
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
Sepehr Assadi, Soheil Behnezhad, Christian Konrad +2
A semi-streaming algorithm in dynamic graph streams processes any -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph…
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For -vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS…
Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
Amir Azarmehr, Soheil Behnezhad, Mohammad Roghani
Maximum matching is one of the most fundamental combinatorial optimization problems with applications in various contexts such as balanced clustering, data mining, resource allocat…
Correlation Clustering Beyond the Pivot Algorithm
Soheil Behnezhad, Moses Charikar, Vincent Cohen-Addad +2
We study the classic correlation clustering in the dynamic setting. Given objects and a complete labeling of the object-pairs as either similar or dissimilar, the goal is to pa…
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
Soheil Behnezhad, Alma Ghafari
We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge inserti…