24 citations · 82 across the 26 of their papers we have counts for
35 papers
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…
Improved Weighted Maximin Share Guarantees for Indivisible Chores
Masoud Seddighin, Saeed Seddighin
We consider the problem of assigning indivisible chores to agents with different entitlements in the maximin share (\MMS) context. While constant-\MMS\ allocations are guaranteed t…
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…
Lower Bound for Online MMS Assignment of Indivisible Chores
Masoud Seddighin, Saeed Seddighin
We consider the problem of online assignment of indivisible chores under \MMS\ criteria. The previous work proves that any deterministic online algorithm for chore division has a c…
Beating the Logarithmic Barrier for the Subadditive Maximin Share Problem
Masoud Seddighin, Saeed Seddighin
We study the problem of fair allocation of indivisible goods for subadditive agents. While constant-\textsf{MMS} bounds have been given for additive and fractionally subadditive ag…
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…
On Complexity of 1-Center in Various Metrics
Amir Abboud, Mohammad Hossein Bateni, Vincent Cohen-Addad +2
We consider the classic 1-center problem: Given a set of points in a metric space find the point in that minimizes the maximum distance to the other points of . We s…
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…
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
François Le Gall, Saeed Seddighin
Longest common substring (LCS), longest palindrome substring (LPS), and Ulam distance (UL) are three fundamental string problems that can be classically solved in near linear time.…
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…
Learning Complexity of Simulated Annealing
Avrim Blum, Chen Dan, Saeed Seddighin
Simulated annealing is an effective and general means of optimization. It is in fact inspired by metallurgy, where the temperature of a material determines its behavior in thermody…
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…
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…
Computing Stackelberg Equilibria of Large General-Sum Games
Avrim Blum, Nika Hagtalab, MohammadTaghi Hajiaghayi +1
We study the computational complexity of finding Stackelberg Equilibria in general-sum games, where the set of pure strategies of the leader and the followers are exponentially lar…
Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani +2
Despite persistent efforts, there is no known technique for obtaining unconditional super-linear lower bounds for the computational complexity of the problems in P. Vassilevska Wil…
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…