65 citations · 69 across the 3 of their papers we have counts for
4 papers
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…
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…
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…
Fast Convergence in the Double Oral Auction
Sepehr Assadi, Sanjeev Khanna, Yang Li +1
A classical trading experiment consists of a set of unit demand buyers and unit supply sellers with identical items. Each agent's value or opportunity cost for the item is their pr…