65 citations · 195 across the 64 of their papers we have counts for
4 papers · 1 filter
Settling the Pass Complexity of Streaming Set Cover
Sepehr Assadi, Janani Sundaresan
In the streaming set cover problem, sets from a universe of size 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 -vertex graph 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 colors, improving upon the "gr…