1 citations · 3 across the 5 of their papers we have counts for
7 papers · 1 filter
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…
Space Complexity of Minimum Cut Problems in Single-Pass Streams
Matthew Ding, Alexandro Garces, Jason Li +4
We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the spec…
New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
Prantar Ghosh, Vihan Shah
We show new lower bounds in the \emph{Merlin-Arthur} (MA) communication model and the related \emph{annotated streaming} or stream verification model. The MA communication model is…
Generalizing Greenwald-Khanna Streaming Quantile Summaries for Weighted Inputs
Sepehr Assadi, Nirmit Joshi, Milind Prabhu +1
Estimating quantiles, like the median or percentiles, is a fundamental task in data mining and data science. A (streaming) quantile summary is a data structure that can process a s…
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 …
Space Optimal Vertex Cover in Dynamic Streams
Kheeran K. Naidu, Vihan Shah
We optimally resolve the space complexity for the problem of finding an -approximate minimum vertex cover (MVC) in dynamic graph streams. We give a randomised algorithm for $…
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…