6 papers
-time Algorithm for Bounded Tree Edit Distance
Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +3
Computing the edit distance of two strings is one of the most basic problems in computer science and combinatorial optimization. Tree edit distance is a natural generalization of e…
Dynamic Subset Sum with Truly Sublinear Processing Time
Hamed Saleh, Saeed Seddighin
Subset sum is a very old and fundamental problem in theoretical computer science. In this problem, items with weights are given as input and the go…
Adaptive Massively Parallel Algorithms for Cut Problems
MohammadTaghi Hajiaghayi, Marina Knittel, Jan Olkowski +1
We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. In 2019, Behnezhad et al. [3] introduced the AMPC model as an extension of the Ma…
Adaptive Massively Parallel Constant-round Tree Contraction
MohammadTaghi Hajiaghayi, Marina Knittel, Hamed Saleh +1
Miller and Reif's FOCS'85 classic and fundamental tree contraction algorithm is a broadly applicable technique for the parallel solution of a large number of tree problems. Additio…
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…
Fair Allocation of Indivisible Items With Externalities
Mohammad Ghodsi, Hamed Saleh, Masoud Seddighin
One of the important yet insufficiently studied subjects in fair allocation is the externality effect among agents. For a resource allocation problem, externalities imply that a bu…