24 citations · 82 across the 26 of their papers we have counts for
18 papers · 1 filter
On the Metric Distortion of the Minimum Spanning Tree Problem
Kian Ghassemi, Masoud Seddighin, Saeed Seddighin
We study the metric distortion of the minimum spanning tree (MST) problem when numerical edge weights are unavailable and each vertex reports only a ranking of the other vertices i…
Barely Monotone (min,+)-Convolution in Truly Subquadratic Time
MohammadTaghi Hajiaghayi, Danny Mittal, Saeed Seddighin
The (min,+)-convolution of two sequences A and B of length n is the sequence C with C[k] = min_{i+j=k} (A[i]+B[j]). For bounded inputs, whose entries are integers in {0,...,O(n)},…
Massively Parallel Algorithms for Huffman Coding
Masoud Seddighin, Saeed Seddighin
Huffman coding is one of the oldest and most fundamental problems in computer science. Given a string of length $\TextLength$ over a general alphabet, the goal is to assign a binar…
Maximizing Social Influence in Almost Linear Time
Saeed Seddighin
Influence maximization is a central algorithmic challenge in network analysis, aiming to identify a set of seed nodes in a graph with nodes and edges that maximizes the…
Dynamic Pattern Matching with Wildcards
Arshia Ataee Naeini, Amir-Parsa Mobed, Masoud Seddighin +1
We study the fully dynamic pattern matching problem where the pattern may contain up to kwildcard symbols, each matching any symbol of the alphabet. Both the text and the pattern a…
Quantum Pattern Matching with Wildcards
Masoud Seddighin, Saeed Seddighin
Pattern matching is one of the fundamental problems in Computer Science. Both the classic version of the problem as well as the more sophisticated version where wildcards can also…
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…
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Aviad Rubinstein, Saeed Seddighin, Zhao Song +1
Longest common subsequence () is a classic and central problem in combinatorial optimization. While admits a quadratic time solution, recent evidence s…
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…
Asymmetric Streaming Algorithms for Edit Distance and LCS
Alireza Farhadi, MohammadTaghi Hajiaghayi, Aviad Rubinstein +1
The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we consider these…
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin +1
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark are popular systems for processing large amounts of data. The design of efficient algorithms in these framew…
Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi +2
The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another…
Stochastic k-Server: How Should Uber Work?
Sina Dehghani, Soheil Ehsani, MohammadTaghi HajiAghayi +2
In this paper, we study a stochastic variant of the celebrated k-server problem. In the k-server problem, we are required to minimize the total movement of k servers that are servi…
Online Weighted Degree-Bounded Steiner Networks via Novel Online Mixed Packing/Covering
Sina Dehghani, Soheil Ehsani, MohammadTaghi Hajiaghayi +3
We design the first online algorithm with poly-logarithmic competitive ratio for the edge-weighted degree-bounded Steiner forest(EW-DB-SF) problem and its generalized variant. We o…