65 citations · 69 across the 3 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2017★ 65 cited
On Estimating Maximum Matching Size in Graph Streams
Sepehr Assadi, Sanjeev Khanna, Yang Li
We study the problem of estimating the maximum matching size in graphs whose edges are revealed in a streaming manner. We consider both insertion-only streams and dynamic streams a…
cs.DS2016
Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem
Sepehr Assadi, Sanjeev Khanna, Yang Li
We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an -approximate set cover (for any $α= o(\sqrt{n…
cs.DS2015
Dynamic Sketching for Graph Optimization Problems with Applications to Cut-Preserving Sketches
Sepehr Assadi, Sanjeev Khanna, Yang Li +1
In this paper, we introduce a new model for sublinear algorithms called \emph{dynamic sketching}. In this model, the underlying data is partitioned into a large \emph{static} part…