SASepehr Assadi

Sepehr Assadi

*This is an algorithmically generated author record based on publicly available information.

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


Sepehr Assadi has a total of 44 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams

    by Sepehr Assadi, Soheil Behnezhad, Christian Konrad, Kheeran Naidu, Janani Sundaresan

    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

    Vizing’s Theorem in Near-Linear Time

    by Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, Tianyi Zhang

    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 .

  • Simple Sublinear Algorithms for $(Δ+1)$ Vertex Coloring via Asymmetric Palette Sparsification

    by Sepehr Assadi, Helia Yazdanyar

    The 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

    A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching

    by Sepehr Assadi

    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

    Covering Approximate Shortest Paths with DAGs

    by Sepehr Assadi, Gary Hoppenworth, Nicole Wein


  • Open Access

    Vizing’s Theorem in Near-Linear Time

    by Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang


  • Open Access

    An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs Using Fast Matrix Multiplication

    by Sepehr Assadi, Vihan Shah

    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.