65 citations · 195 across the 64 of their papers we have counts for
9 papers · 1 filter
A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
Sepehr Assadi, Michael Kapralov, Sanjeev Khanna
In the subgraph counting problem, we are given a input graph and a target graph ; the goal is to estimate the number of occurrences of in . Our focus here is on…
Secretary Ranking with Minimal Inversions
Sepehr Assadi, Eric Balkanski, Renato Paes Leme
We study a twist on the classic secretary problem, which we term the secretary ranking problem: elements from an ordered set arrive in random order and instead of picking the maxim…
Towards a Unified Theory of Sparsification for Matching Problems
Sepehr Assadi, Aaron Bernstein
In this paper, we present a construction of a `matching sparsifier', that is, a sparse subgraph of the given graph that preserves large matchings approximately and is robust to mod…
Stochastic Submodular Cover with Limited Adaptivity
Arpit Agarwal, Sepehr Assadi, Sanjeev Khanna
In the submodular cover problem, we are given a non-negative monotone submodular function over a ground set of items, and the goal is to choose a smallest subset $S \subset…
Sublinear Algorithms for Vertex Coloring
Sepehr Assadi, Yu Chen, Sanjeev Khanna
Any graph with maximum degree admits a proper vertex coloring with colors that can be found via a simple sequential greedy algorithm in linear time and space. But can on…
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber +1
The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of…
Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
Sepehr Assadi, Xiaorui Sun, Omri Weinstein
A fundamental question that shrouds the emergence of massively parallel computing (MPC) platforms is how can the additional power of the MPC paradigm be leveraged to achieve faster…
Fully Dynamic Maximal Independent Set with Sublinear Update Time
Sepehr Assadi, Krzysztof Onak, Baruch Schieber +1
A maximal independent set (MIS) can be maintained in an evolving -edge graph by simply recomputing it from scratch in time after each update. But can it be maintained in…
Tight Bounds on the Round Complexity of the Distributed Maximum Coverage Problem
Sepehr Assadi, Sanjeev Khanna
We study the maximum -set coverage problem in the following distributed setting. A collection of sets over a universe is partitioned across machines a…