65 citations · 195 across the 64 of their papers we have counts for
9 papers · 1 filter
Passes is Optimal for Semi-Streaming Maximal Independent Set
Sepehr Assadi, Christian Konrad, Kheeran K. Naidu +1
In the semi-streaming model for processing massive graphs, an algorithm makes multiple passes over the edges of a given -vertex graph and is tasked with computing the solution t…
Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams
Sepehr Assadi, Gillat Kol, Zhijun Zhang
The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over d…
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…
The Best Arm Evades: Near-optimal Multi-pass Streaming Lower Bounds for Pure Exploration in Multi-armed Bandits
Sepehr Assadi, Chen Wang
We give a near-optimal sample-pass trade-off for pure exploration in multi-armed bandits (MABs) via multi-pass streaming algorithms: any streaming algorithm with sublinear memory t…
A Simple -Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching
Sepehr Assadi
We present a simple semi-streaming algorithm for -approximation of bipartite matching in passes. This matches the performance of state-of-the-art "-eff…
Evaluating Stability in Massive Social Networks: Efficient Streaming Algorithms for Structural Balance
Vikrant Ashvinkumar, Sepehr Assadi, Chengyuan Deng +2
Structural balance theory studies stability in networks. Given a -vertex complete graph whose edges are labeled positive or negative, the graph is considered \emph{bal…
(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…
All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method
Sepehr Assadi, Aaron Bernstein, Zachary Langley
In the weighted load balancing problem, the input is an -vertex bipartite graph between a set of clients and a set of servers, and each client comes with some nonnegative real w…