65 citations · 195 across the 64 of their papers we have counts for
12 papers · 1 filter
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
Sepehr Assadi, Amit Chakrabarti, Prantar Ghosh +1
In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially…
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 …
On Constructing Spanners from Random Gaussian Projections
Sepehr Assadi, Michael Kapralov, Huacheng Yu
Graph sketching is a powerful paradigm for analyzing graph structure via linear measurements introduced by Ahn, Guha, and McGregor (SODA'12) that has since found numerous applicati…
Rounds vs Communication Tradeoffs for Maximal Independent Sets
Sepehr Assadi, Gillat Kol, Zhijun Zhang
We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There are players corresponding…
Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting
Sepehr Assadi, Hoai-An Nguyen
The -index is a metric used to measure the impact of a user in a publication setting, such as a member of a social network with many highly liked posts or a researcher in an aca…
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…
Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds
Sepehr Assadi, Vaggos Chatziafratis, Jakub Łącki +2
The Hierarchical Clustering (HC) problem consists of building a hierarchy of clusters to represent a given dataset. Motivated by the modern large-scale applications, we study the p…
Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling
Sepehr Assadi, Vikram Kher, George Li +1
Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optima…
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for -Coloring
Sepehr Assadi, Pankaj Kumar, Parth Mittal
Every graph with maximum degree can be colored with colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in…
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…