Sepehr Assadi
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Sepehr Assadi has a total of 44 co-authors. Here are the top co-authors by number of shared publications:
- Sanjeev Khanna
School of Engineering and Applied Sciences University of Pennsylvania Philadelphia PA
9 shared publications - Yang Li
Department of Computer and Information Science University of Pennsylvania
6 shared publications - Janani Sundaresan
University of Waterloo, Waterloo, Canada
3 shared publications - Soheil Behnezhad
Northeastern University, Boston, USA
3 shared publications - Aaron Bernstein
Rutgers University
2 shared publications - Gillat Kol
Princeton University, Princeton, USA
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. 1651-1659
Settling the Pass Complexity of Streaming Set Cover
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 1651-1659
Open AccessSettling the Pass Complexity of Streaming Set Cover
- Open Access
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 979-990
Semi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
- 9 June 2026
- Published by Association for Computing Machinery (ACM)
- p. 979-990
Open AccessSemi-streaming Matching in a Single Pass: A New Framework for Lower Bounds via Blueprints
- 29 January 2026
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 5
Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette SparsificationThe palette sparsification theorem (PST) of Assadi, Chen, and Khanna (SODA 2019) states that in every graph $G$ with maximum degree $Δ$, sampling a list of $O(\log{n})$ colors from $\{1,\ldots,Δ+1\}$ for every vertex independently and uniformly, with high probability, allows for finding a $(Δ+1)$ vertex coloring of $G$ by coloring each vertex only from its sampled list. PST naturally leads to a host of sublinear algorithms for $(Δ+1)$ vertex coloring, including in semi-streaming, sublinear time, and MPC models, which are all proven to be nearly optimal, and in the case of the former two are the only known sublinear algorithms for this problem. While being a quite natural and simple-to-state theorem, PST suffers from two drawbacks. Firstly, all its known proofs require technical arguments that rely on sophisticated graph decompositions and probabilistic arguments. Secondly, finding the coloring of the graph from the sampled lists in an efficient manner requires a considerably complicated algorithm. We show that a natural weakening of PST addresses both these drawbacks while still leading to sublinear algorithms of similar quality (up to polylog factors). In particular, we prove an asymmetric palette sparsification theorem (APST) that allows for list sizes of the vertices to have different sizes and only bounds the average size of these lists. The benefit of this weaker requirement is that we can now easily show the graph can be $(Δ+1)$ colored from the sampled lists using the standard greedy coloring algorithm. This way, we can recover nearly-optimal bounds for $(Δ+1)$ vertex coloring in all the aforementioned models using algorithms that are much simpler to implement and analyze. 18 pages. This is the TheoretiCS journal version- 29 January 2026
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 5
Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette SparsificationThe palette sparsification theorem (PST) of Assadi, Chen, and Khanna (SODA 2019) states that in every graph $G$ with maximum degree $Δ$, sampling a list of $O(\log{n})$ colors from $\{1,\ldots,Δ+1\}$ for every vertex independently and uniformly, with high probability, allows for finding a $(Δ+1)$ vertex coloring of $G$ by coloring each vertex only from its sampled list. PST naturally leads to a host of sublinear algorithms for $(Δ+1)$ vertex coloring, including in semi-streaming, sublinear time, and MPC models, which are all proven to be nearly optimal, and in the case of the former two are the only known sublinear algorithms for this problem. While being a quite natural and simple-to-state theorem, PST suffers from two drawbacks. Firstly, all its known proofs require technical arguments that rely on sophisticated graph decompositions and probabilistic arguments. Secondly, finding the coloring of the graph from the sampled lists in an efficient manner requires a considerably complicated algorithm. We show that a natural weakening of PST addresses both these drawbacks while still leading to sublinear algorithms of similar quality (up to polylog factors). In particular, we prove an asymmetric palette sparsification theorem (APST) that allows for list sizes of the vertices to have different sizes and only bounds the average size of these lists. The benefit of this weaker requirement is that we can now easily show the graph can be $(Δ+1)$ colored from the sampled lists using the standard greedy coloring algorithm. This way, we can recover nearly-optimal bounds for $(Δ+1)$ vertex coloring in all the aforementioned models using algorithms that are much simpler to implement and analyze. 18 pages. This is the TheoretiCS journal version- Open Access
- 1 August 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
We present a simple semi-streaming algorithm for $(1-ε)$-approximation of bipartite matching in $O(\log{\!(n)}/ε)$ passes. This matches the performance of state-of-the-art "$ε$-efficient" algorithms -- the ones with much better dependence on $ε$ albeit with some mild dependence on $n$ -- while being considerably simpler. The algorithm relies on a direct application of the multiplicative weight update method with a self-contained primal-dual analysis that can be of independent interest. To show case this, we use the same ideas, alongside standard tools from matching theory, to present an equally simple semi-streaming algorithm for $(1-ε)$-approximation of weighted matchings in general (not necessarily bipartite) graphs, again in $O(\log{\!(n)}/ε)$ passes.25 pages. This is the TheoretiCS journal version- 1 August 2025
- Published by Centre pour la Communication Scientifique Directe (CCSD) in TheoretiCS
- Vol. ume 4
Open AccessA Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
We present a simple semi-streaming algorithm for $(1-ε)$-approximation of bipartite matching in $O(\log{\!(n)}/ε)$ passes. This matches the performance of state-of-the-art "$ε$-efficient" algorithms -- the ones with much better dependence on $ε$ albeit with some mild dependence on $n$ -- while being considerably simpler. The algorithm relies on a direct application of the multiplicative weight update method with a self-contained primal-dual analysis that can be of independent interest. To show case this, we use the same ideas, alongside standard tools from matching theory, to present an equally simple semi-streaming algorithm for $(1-ε)$-approximation of weighted matchings in general (not necessarily bipartite) graphs, again in $O(\log{\!(n)}/ε)$ passes.25 pages. This is the TheoretiCS journal version - Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2269-2280
Covering Approximate Shortest Paths with DAGs
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2269-2280
Open AccessCovering Approximate Shortest Paths with DAGs
- 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. 417-428
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 417-428
Open AccessCorrelation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
- Open Access
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-24
An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication
We study subgraph counting over fully dynamic graphs, which undergo edge insertions and deletions. Counting subgraphs is a fundamental problem in graph theory with numerous applications across various fields, including database theory, social network analysis, and computational biology. In database theory, we can use dynamic subgraph counting algorithms on layered graphs to maintain the sizes of joins of databases that undergo updates. Specifically, the problem of finding the number of elements in a cyclic join of size k is equivalent to counting the number of k-cycles in k-layered graphs. For example, let R, S, and T be relations that have schemas (A, B), (B, C), and (C, A) respectively. Then the size of the join of R with S with T is given by the number of triangles in the corresponding layered graph where there is a layer for each attribute, the vertices are the attribute values and the edges represent the tuples of attribute values in the relations. Maintaining the number of triangles in fully dynamic graphs is very well studied and has an upper bound of O(√m) for the update time [KNN+20]. There is also a conditional lower bound of Ω(m 1/2-γ ) for any constant γ>0, for the update time [HKNS15] under the Online Matrix-Vector (OMv) conjecture implying that O(√m) is the ''right answer' for the update time of counting triangles. More recently, [HHH22] studied the problem of maintaining the number of 4-cycles in fully dynamic graphs and designed an algorithm with O(m 2/3 ) update time which is a natural generalization of the approach for counting triangles. They also studied the problem of counting 4-cliques showing that the folklore upper bound of O(m) for the update time is tight under the static combinatorial 4-clique conjecture by giving a lower bound of Ω(m 1-γ ) for any γ>0. Thus, it seems natural that O(m 2/3 ) might be the correct answer for the complexity of the update time for counting 4-cycles. In this work, we present an improved algorithm for maintaining the number of 4-cycles in fully dynamic graphs. Our algorithm achieves a worst-case update time of O(m 2/3-ε ) for some constant ε>0. We also show that the problem of counting 4-cycles is equivalent in layered graphs and general graphs. Our approach crucially uses fast matrix multiplication and leverages recent developments therein to get an improved runtime. Using the current best value of the matrix multiplication exponent ω=2.371339 we get ε=0.009811 and if we assume the best possible exponent i.e. ω=2 then we get ε=1/24. There is also a lower bound of Ω(m 1/2-γ ) for any constant γ>0, for the update time [HKNS15,HHH22], so there is still a big gap between the best-known upper and lower bounds. The key message of our paper is demonstrating that O(m 2/3 ) is not the correct answer for the complexity of the update time.
- 9 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (2) , 1-24
Open AccessAn Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication
We study subgraph counting over fully dynamic graphs, which undergo edge insertions and deletions. Counting subgraphs is a fundamental problem in graph theory with numerous applications across various fields, including database theory, social network analysis, and computational biology. In database theory, we can use dynamic subgraph counting algorithms on layered graphs to maintain the sizes of joins of databases that undergo updates. Specifically, the problem of finding the number of elements in a cyclic join of size k is equivalent to counting the number of k-cycles in k-layered graphs. For example, let R, S, and T be relations that have schemas (A, B), (B, C), and (C, A) respectively. Then the size of the join of R with S with T is given by the number of triangles in the corresponding layered graph where there is a layer for each attribute, the vertices are the attribute values and the edges represent the tuples of attribute values in the relations. Maintaining the number of triangles in fully dynamic graphs is very well studied and has an upper bound of O(√m) for the update time [KNN+20]. There is also a conditional lower bound of Ω(m 1/2-γ ) for any constant γ>0, for the update time [HKNS15] under the Online Matrix-Vector (OMv) conjecture implying that O(√m) is the ''right answer' for the update time of counting triangles. More recently, [HHH22] studied the problem of maintaining the number of 4-cycles in fully dynamic graphs and designed an algorithm with O(m 2/3 ) update time which is a natural generalization of the approach for counting triangles. They also studied the problem of counting 4-cliques showing that the folklore upper bound of O(m) for the update time is tight under the static combinatorial 4-clique conjecture by giving a lower bound of Ω(m 1-γ ) for any γ>0. Thus, it seems natural that O(m 2/3 ) might be the correct answer for the complexity of the update time for counting 4-cycles. In this work, we present an improved algorithm for maintaining the number of 4-cycles in fully dynamic graphs. Our algorithm achieves a worst-case update time of O(m 2/3-ε ) for some constant ε>0. We also show that the problem of counting 4-cycles is equivalent in layered graphs and general graphs. Our approach crucially uses fast matrix multiplication and leverages recent developments therein to get an improved runtime. Using the current best value of the matrix multiplication exponent ω=2.371339 we get ε=0.009811 and if we assume the best possible exponent i.e. ω=2 then we get ε=1/24. There is also a lower bound of Ω(m 1/2-γ ) for any constant γ>0, for the update time [HKNS15,HHH22], so there is still a big gap between the best-known upper and lower bounds. The key message of our paper is demonstrating that O(m 2/3 ) is not the correct answer for the complexity of the update time.