Soheil Behnezhad
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Soheil Behnezhad has a total of 25 co-authors. Here are the top co-authors by number of shared publications:
- Sepehr Assadi
University of Waterloo, Waterloo, Canada
3 shared publications - Amir Azarmehr
Northeastern University, Boston, USA
2 shared publications - Martín Costa
University of Warwick, Coventry, United Kingdom
2 shared publications - Sayan Bhattacharya
University of Warwick
2 shared publications - Shay Solomon
Tel Aviv University, Tel Aviv, Israel
2 shared publications - Tianyi Zhang
State Key Laboratory for Novel Software Technology, Nanjing University
2 shared publications
Latest Publications
- Open Access
- 16 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (4) , 1-83
Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
A semi-streaming algorithm in dynamic graph streams processes any n -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O ( n · polylog( n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general. We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds: • We present a randomized sketching based semi-streaming algorithm for O (1)-approximation of maximum matching in dynamic streams using O (log log n ) passes. The approximation ratio of this algorithm can be improved to (1 + ε) for any fixed ε > 0 even on weighted graphs using standard techniques. This exponentially improves upon several O (log n ) pass algorithms developed for this problem since the introduction of the dynamic graph streaming model. • We prove that any semi-streaming algorithm (not only sketching based) for O (1)-approximation of maximum matching in dynamic streams requires Ω (log log n ) passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area.
- 16 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (4) , 1-83
Open AccessSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
A semi-streaming algorithm in dynamic graph streams processes any n -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph and using O ( n · polylog( n )) space. Semi-streaming algorithms for dynamic streams were first obtained in the seminal work of Ahn, Guha, and McGregor in 2012, alongside the introduction of the graph sketching technique, which remains the de facto way of designing algorithms in this model and a highly popular technique for designing graph algorithms in general. We settle the pass complexity of approximating maximum matchings in dynamic streams via semi-streaming algorithms by improving the state-of-the-art in both upper and lower bounds: • We present a randomized sketching based semi-streaming algorithm for O (1)-approximation of maximum matching in dynamic streams using O (log log n ) passes. The approximation ratio of this algorithm can be improved to (1 + ε) for any fixed ε > 0 even on weighted graphs using standard techniques. This exponentially improves upon several O (log n ) pass algorithms developed for this problem since the introduction of the dynamic graph streaming model. • We prove that any semi-streaming algorithm (not only sketching based) for O (1)-approximation of maximum matching in dynamic streams requires Ω (log log n ) passes. This presents the first multi-pass lower bound for this problem, which is already also optimal, settling a longstanding open question in this area.
- Open Access
- 16 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (3) , 1-53
Vizing’s Theorem in Near-Linear Time
Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem .- 16 June 2026
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 73 (3) , 1-53
Open AccessVizing’s Theorem in Near-Linear Time
Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem . - Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2118-2129
Half-Approximating Maximum Dicut in the Streaming Setting
We study streaming algorithms for the maximum directed cut problem. The edges of an n-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With O(n) space, a (1−ε)-approximation can be trivially obtained for any fixed ε > 0 using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., n1−Ω(1)) space. A lower bound of Kapralov and Krachun (STOC’19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS’23). The same authors later obtained a (1/2−ε)-approximation, assuming that the graph is constant-degree (SODA’25). In this paper, we show that for any ε > 0, a (1/2−ε)-approximation of maximum dicut value can be obtained with n1−Ωε(1) space in *general graphs*. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm.
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 2118-2129
Open AccessHalf-Approximating Maximum Dicut in the Streaming Setting
We study streaming algorithms for the maximum directed cut problem. The edges of an n-vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate the value of the maximum directed cut using a single pass and small space. With O(n) space, a (1−ε)-approximation can be trivially obtained for any fixed ε > 0 using additive cut sparsifiers. The question that has attracted significant attention in the literature is the best approximation achievable by algorithms that use truly sublinear (i.e., n1−Ω(1)) space. A lower bound of Kapralov and Krachun (STOC’19) implies .5-approximation is the best one can hope for. The current best algorithm for general graphs obtains a .485-approximation due to the work of Saxena, Singer, Sudan, and Velusamy (FOCS’23). The same authors later obtained a (1/2−ε)-approximation, assuming that the graph is constant-degree (SODA’25). In this paper, we show that for any ε > 0, a (1/2−ε)-approximation of maximum dicut value can be obtained with n1−Ωε(1) space in *general graphs*. This shows that the lower bound of Kapralov and Krachun is generally tight, settling the approximation complexity of this fundamental problem. The key to our result is a careful analysis of how correlation propagates among high- and low-degree vertices, when simulating a suitable local algorithm.
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Vizing’s Theorem in Near-Linear Time
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 24-35
Open AccessVizing’s Theorem in Near-Linear Time
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1055-1066
Stochastic Matching via In-n-Out Local Computation Algorithms
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 1055-1066
Open AccessStochastic Matching via In-n-Out Local Computation Algorithms
- Open Access
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 444-454
Approximating Maximum Matching Requires Almost Quadratic Time
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For n-vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS’23] (BKS) showed that an estimate that is within є n of the optimal solution can be achieved in n2−Ωє(1) time, where n is the number of vertices. While this is subquadratic in n for any fixed є > 0, it gets closer and closer to the trivial Θ(n2) time algorithm that reads the entire input as є is made smaller and smaller. In this work, we close this gap and show that the algorithm of BKS is close to optimal. In particular, we prove that for any fixed δ > 0, there is another fixed є = є(δ) > 0 such that estimating the size of maximum matching within an additive error of є n requires Ω(n2−δ) time in the adjacency list model.
- 10 June 2024
- Published by Association for Computing Machinery (ACM)
- p. 444-454
Open AccessApproximating Maximum Matching Requires Almost Quadratic Time
We study algorithms for estimating the size of maximum matching. This problem has been subject to extensive research. For n-vertex graphs, Bhattacharya, Kiss, and Saranurak [FOCS’23] (BKS) showed that an estimate that is within є n of the optimal solution can be achieved in n2−Ωє(1) time, where n is the number of vertices. While this is subquadratic in n for any fixed є > 0, it gets closer and closer to the trivial Θ(n2) time algorithm that reads the entire input as є is made smaller and smaller. In this work, we close this gap and show that the algorithm of BKS is close to optimal. In particular, we prove that for any fixed δ > 0, there is another fixed є = є(δ) > 0 such that estimating the size of maximum matching within an additive error of є n requires Ω(n2−δ) time in the adjacency list model.
- Open Access
- 11 October 2023
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 70 (5) , 1-18
Exponentially Faster Massively Parallel Maximal Matching
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n 1+Ω (1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [ 15 ]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O (log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O (log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds.
- 11 October 2023
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 70 (5) , 1-18
Open AccessExponentially Faster Massively Parallel Maximal Matching
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, we still have a limited understanding of maximal matching which is one of the central problems of parallel and distributed computing. All known MPC algorithms for maximal matching either take polylogarithmic time which is considered inefficient, or require a strictly super-linear space of n 1+Ω (1) per machine. In this work, we close this gap by providing a novel analysis of an extremely simple algorithm, which is a variant of an algorithm conjectured to work by Czumaj, Lacki, Madry, Mitrovic, Onak, and Sankowski [ 15 ]. The algorithm edge-samples the graph, randomly partitions the vertices, and finds a random greedy maximal matching within each partition. We show that this algorithm drastically reduces the vertex degrees. This, among other results, leads to an O (log log Δ) round algorithm for maximal matching with O(n) space (or even mildly sublinear in n using standard techniques). As an immediate corollary, we get a 2 approximate minimum vertex cover in essentially the same rounds and space, which is the optimal approximation factor under standard assumptions. We also get an improved O (log log Δ) round algorithm for 1 + ε approximate matching. All these results can also be implemented in the congested clique model in the same number of rounds.
- Open Access
Almost 3-Approximate Correlation Clustering in Constant Rounds
We study parallel algorithms for correlation clustering. Each pair among $n$ objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels. Our main result is an algorithm that for any $\epsilon > 0$ obtains a $(3+\epsilon)$-approximation in $O(1/\epsilon)$ rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm's round-complexity is essentially constant. To achieve this result, we introduce a simple $O(1/\epsilon)$-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a $(3+\epsilon)$-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [STOC'09] on bounding the "query complexity" of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm.Open AccessAlmost 3-Approximate Correlation Clustering in Constant Rounds
We study parallel algorithms for correlation clustering. Each pair among $n$ objects is labeled as either "similar" or "dissimilar". The goal is to partition the objects into arbitrarily many clusters while minimizing the number of disagreements with the labels. Our main result is an algorithm that for any $\epsilon > 0$ obtains a $(3+\epsilon)$-approximation in $O(1/\epsilon)$ rounds (of models such as massively parallel computation, local, and semi-streaming). This is a culminating point for the rich literature on parallel correlation clustering. On the one hand, the approximation (almost) matches a natural barrier of 3 for combinatorial algorithms. On the other hand, the algorithm's round-complexity is essentially constant. To achieve this result, we introduce a simple $O(1/\epsilon)$-round parallel algorithm. Our main result is to provide an analysis of this algorithm, showing that it achieves a $(3+\epsilon)$-approximation. Our analysis draws on new connections to sublinear-time algorithms. Specifically, it builds on the work of Yoshida, Yamamoto, and Ito [STOC'09] on bounding the "query complexity" of greedy maximal independent set. To our knowledge, this is the first application of this method in analyzing the approximation ratio of any algorithm. - Open Access
- 1 September 2020
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 13 (13) , 3588-3602
Parallel graph algorithms in constant adaptive rounds
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 focus on the Adaptive Massively Parallel Computation (AMPC) model, which is a theoretical model that captures MapReduce-like computation augmented with a distributed hash table. We show the first AMPC algorithms for all of the studied problems that run in a constant number of rounds and use only O(nϵ) space per machine, where 0 < ϵ < 1. Our results improve both upon the previous results in the AMPC model, as well as the best-known results in the MPC model, which is the theoretical model underpinning many popular distributed computation frameworks, such as MapReduce, Hadoop, Beam, Pregel and Giraph. Finally, we provide an empirical comparison of the algorithms in the MPC and AMPC models in a fault-tolerant distributed computation environment. We empirically evaluate our algorithms on a set of large real-world graphs and show that our AMPC algorithms can achieve improvements in both running time and round-complexity over optimized MPC baselines.
- 1 September 2020
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 13 (13) , 3588-3602
Open AccessParallel graph algorithms in constant adaptive rounds
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 focus on the Adaptive Massively Parallel Computation (AMPC) model, which is a theoretical model that captures MapReduce-like computation augmented with a distributed hash table. We show the first AMPC algorithms for all of the studied problems that run in a constant number of rounds and use only O(nϵ) space per machine, where 0 < ϵ < 1. Our results improve both upon the previous results in the AMPC model, as well as the best-known results in the MPC model, which is the theoretical model underpinning many popular distributed computation frameworks, such as MapReduce, Hadoop, Beam, Pregel and Giraph. Finally, we provide an empirical comparison of the algorithms in the MPC and AMPC models in a fault-tolerant distributed computation environment. We empirically evaluate our algorithms on a set of large real-world graphs and show that our AMPC algorithms can achieve improvements in both running time and round-complexity over optimized MPC baselines.