Sepehr Assadi

Settling the Pass Complexity of Streaming Set Cover

Sepehr Assadi, Janani Sundaresan

In the streaming set cover problem, $m$ sets from a universe of size $n$ are arriving one by one in a stream, and the algorithm is allowed to process the stream using one or a few…

Semi-Streaming Matching in a Single Pass II: Greedy is Optimal

Sepehr Assadi, Max Jiang, Mars Xiang

We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the o…

Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints

Sepehr Assadi, Max Jiang, Mars Xiang

In the semi-streaming model, we have an $n$ -vertex graph $G = (V, E)$ whose edges arrive in an arbitrary order in a stream. The goal is to make one or a few passes over the stream, us…

Fully Dynamic Algorithms for Coloring Triangle-Free Graphs

Sepehr Assadi, Helia Yazdanyar

A celebrated result of Johansson in graph theory states that every triangle-free graph of maximum degree $Δ$ can be properly colored with $O (Δ/ ln Δ)$ colors, improving upon the "gr…

Coloring Graphs with Few Colors in the Streaming Model

Sepehr Assadi, Janani Sundaresan, Helia Yazdanyar

We study graph coloring problems in the streaming model, where the goal is to process an $n$ -vertex graph whose edges arrive in a stream, using a limited space that is smaller than…

Vizing's Theorem in Deterministic Almost-Linear Time

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3

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's original proof is easily transl…

Better Bounds for Semi-Streaming Single-Source Shortest Paths

Sepehr Assadi, Gary Hoppenworth, Janani Sundaresan

In the semi-streaming model, an algorithm must process any $n$ -vertex graph by making one or few passes over a stream of its edges, use $O (n \cdot polylog n)$ words of space…

Covering Approximate Shortest Paths with DAGs

Sepehr Assadi, Gary Hoppenworth, Nicole Wein

We define and study analogs of probabilistic tree embedding and tree cover for directed graphs. We define the notion of a DAG cover of a general directed graph $G$ : a small collect…

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

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 applica…

Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms

Sepehr Assadi, Sanjeev Khanna, Aaron Putterman

Correlation clustering is a widely-used approach for clustering large data sets based only on pairwise similarity information. In recent years, there has been a steady stream of be…

Distributed Triangle Detection is Hard in Few Rounds

Sepehr Assadi, Janani Sundaresan

In the distributed triangle detection problem, we have an $n$ -vertex network $G = (V, E)$ with one player for each vertex of the graph who sees the edges incident on the vertex. The p…

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

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 (lo g n)$ colors from…

Streaming and Communication Complexity of Load-Balancing via Matching Contractors

Sepehr Assadi, Aaron Bernstein, Zachary Langley +2

In the load-balancing problem, we have an $n$ -vertex bipartite graph $G = (L, R, E)$ between a set of clients and servers. The goal is to find an assignment of all clients to the ser…

cs.DS2024★ 1 cited

Vizing's Theorem in Near-Linear Time

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya +3

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 i…

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 $n$ -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph…

cs.DS2024★ 1 cited

Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemeredi Graphs

Sepehr Assadi, Sanjeev Khanna, Peter Kiss

In a very recent breakthrough, Behnezhad and Ghafari [FOCS'24] developed a novel fully dynamic randomized algorithm for maintaining a $(1 - ε)$ -approximation of maximum matching with…

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy

Sepehr Assadi, Prantar Ghosh, Bruno Loff +2

The following question arises naturally in the study of graph streaming algorithms: "Is there any graph problem which is "not too hard", in that it can be solved efficiently with t…