1 citations · 1 across the 6 of their papers we have counts for
9 papers
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…
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…
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…
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 -vertex graph by making one or multiple passes over a stream of insertions and deletions to edges of the graph…
Optimal Communication Complexity of Chained Index
Janani Sundaresan
We study the CHAIN communication problem introduced by Cormode et al. [ICALP 2019]. It is a generalization of the well-studied INDEX problem. For , in CHAIN, there…
Passes is Optimal for Semi-Streaming Maximal Independent Set
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu +1
In the semi-streaming model for processing massive graphs, an algorithm makes multiple passes over the edges of a given -vertex graph and is tasked with computing the solution t…
Hidden Permutations to the Rescue: Multi-Pass Semi-Streaming Lower Bounds for Approximate Matchings
Sepehr Assadi, Janani Sundaresan
We prove that any semi-streaming algorithm for -approximation of maximum bipartite matching requires \[ Ω(\frac{\log{(1/ε)}}{\log{(1/β)}}) \] passes, where is t…
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi, Janani Sundaresan
We continue the study of the communication complexity of gap cycle counting problems. These problems have been introduced by Verbin and Yu [SODA 2011] and have found numerous appli…