46 citations · 101 across the 26 of their papers we have counts for
4 papers · 1 filter
String Matching with Wildcards in the Massively Parallel Computation Model
MohammadTaghi Hajiaghayi, Hamed Saleh, Saeed Seddighin +1
We study distributed algorithms for string matching problem in presence of wildcard characters. Given a string T (a text), we look for all occurrences of another string P (a patter…
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…
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…