21 citations · 41 across the 17 of their papers we have counts for
36 papers
Tight Bounds for Vertex Connectivity in Dynamic Streams
Sepehr Assadi, Vihan Shah
We present a streaming algorithm for the vertex connectivity problem in dynamic streams with a (nearly) optimal space bound: for any -vertex graph and any integer …
On Constructing Spanners from Random Gaussian Projections
Sepehr Assadi, Michael Kapralov, Huacheng Yu
Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applicati…
Rounds vs Communication Tradeoffs for Maximal Independent Sets
Sepehr Assadi, Gillat Kol, Zhijun Zhang
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are players corresponding…
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting
Sepehr Assadi, Hoai-An Nguyen
The -index is a metric used to measure the impact of a user in a publication setting, such as a member of a social network with many highly liked posts or a researcher in an aca…
An Asymptotically Optimal Algorithm for Maximum Matching in Dynamic Streams
Sepehr Assadi, Vihan Shah
We present an algorithm for the maximum matching problem in dynamic (insertion-deletions) streams with *asymptotically optimal* space complexity: for any -vertex graph, our algo…
Deterministic Graph Coloring in the Streaming Model
Sepehr Assadi, Andrew Chen, Glenn Sun
Recent breakthroughs in graph streaming have led to the design of single-pass semi-streaming algorithms for various graph coloring problems such as -coloring, degeneracy-col…