4 citations · 14 across the 8 of their papers we have counts for
15 papers
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…
Optimal Space and Time for Streaming Pattern Matching
Tung Mai, Anup Rao, Ryan A. Rossi +1
In this work, we study longest common substring, pattern matching, and wildcard pattern matching in the asymmetric streaming model. In this streaming model, we have random access t…
Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
Michael Mitzenmacher, Saeed Seddighin
In this paper, we provide new approximation algorithms for dynamic variations of the longest increasing subsequence (\textsf{LIS}) problem, and the complementary distance to monoto…
Erdös-Szekeres Partitioning Problem
Michael Mitzenmacher, Saeed Seddighin
In this note, we present a substantial improvement on the computational complexity of the Erdös-Szekeres partitioning problem and review recent works on dynamic \textsf{LIS}.
Improved Dynamic Algorithms for Longest Increasing Subsequence
Tomasz Kociumaka, Saeed Seddighin
We study dynamic algorithms for the longest increasing subsequence (\textsf{LIS}) problem. A dynamic \textsf{LIS} algorithm maintains a sequence subject to operations of the follow…
Approximating LCS in Linear Time: Beating the Barrier
MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin +1
Longest common subsequence (LCS) is one of the most fundamental problems in combinatorial optimization. Apart from theoretical importance, LCS has enormous applications in bioinfor…