From the 2 of 13 linked papers with an AI index.
13 papers
Semi-Streaming Matching in a Single Pass II: Greedy is Optimal
Sepehr Assadi, Max Jiang, Mars Xiang
The paper proves that no single-pass semi‑streaming algorithm can achieve better than a 1/2 approximation for maximum matching, establishing the greedy algorithm as optimal and als…
Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints
Sepehr Assadi, Max Jiang, Mars Xiang
The paper presents a new blueprint-based framework for proving lower bounds on the approximation ratio of single‑pass semi‑streaming algorithms for maximum matching, simplifying pr…
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 colors, improving upon the…
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 fro…
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…
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…