65 citations · 66 across the 4 of their papers we have counts for
7 papers
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…
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 Monotone Minimal Perfect Hashing
Sepehr Assadi, Martin Farach-Colton, William Kuszmaul
The monotone minimal perfect hash function (MMPHF) problem is the following indexing problem. Given a set of distinct keys from a universe of size $…
On Regularity Lemma and Barriers in Streaming and Dynamic Matching
Sepehr Assadi, Soheil Behnezhad, Sanjeev Khanna +1
We present a new approach for finding matchings in dense graphs by building on Szemerédi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improveme…
Decremental Matching in General Graphs
Sepehr Assadi, Aaron Bernstein, Aditi Dudeja
We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph , while the adversary makes changes to the edges of the graph. The goal is to…