12 citations · 29 across the 37 of their papers we have counts for
6 papers · 1 filter
Fully Dynamic Matching: Beating 2-Approximation in Update Time
Soheil Behnezhad, Jakub Łącki, Vahab Mirrokni
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and de…
Near-Optimal Massively Parallel Graph Connectivity
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +2
Identifying the connected components of a graph, apart from being a fundamental problem with countless applications, is a key primitive for many other algorithms. In this paper, we…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
Massively Parallel Computation via Remote Memory Access
Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari +3
We introduce the Adaptive Massively Parallel Computation (AMPC) model, which is an extension of the Massively Parallel Computation (MPC) model. At a high level, the AMPC model stre…
Optimal Strategies of Blotto Games: Beyond Convexity
Soheil Behnezhad, Avrim Blum, Mahsa Derakhshan +3
The Colonel Blotto game, first introduced by Borel in 1921, is a well-studied game theory classic. Two colonels each have a pool of troops that they divide simultaneously among a s…
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
The study of approximate matching in the Massively Parallel Computations (MPC) model has recently seen a burst of breakthroughs. Despite this progress, however, we still have a far…