65 citations · 195 across the 64 of their papers we have counts for
8 papers · 1 filter
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 -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 -vertex -edge graph of maximum degree can be edge colored using at most 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 -vertex graph by making one or few passes over a stream of its edges, use 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 : 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 -vertex network with one player for each vertex of the graph who sees the edges incident on the vertex. The p…
Simple Sublinear Algorithms for 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 with maximum degree , sampling a list of colors from…