
Optimal Space and Time for Streaming Pattern Matching
In this work, we study longest common substring, pattern matching, and w...
read it

Dynamic Longest Increasing Subsequence and the ErdösSzekeres Partitioning Problem
In this paper, we provide new approximation algorithms for dynamic varia...
read it

Improved Dynamic Algorithms for Longest Increasing Subsequence
We study dynamic algorithms for the longest increasing subsequence (LIS)...
read it

ErdösSzekeres Partitioning Problem
In this note, we present a substantial improvement on the computational ...
read it

Quantum Meets Finegrained Complexity: Sublinear Time Quantum Algorithms for String Problems
Longest common substring (LCS), longest palindrome substring (LPS), and ...
read it

Approximating LCS in Linear Time: Beating the √(n) Barrier
Longest common subsequence (LCS) is one of the most fundamental problems...
read it

Learning Complexity of Simulated Annealing
Simulated annealing is an effective and general means of optimization. I...
read it

Asymmetric Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
read it

Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
read it

Massively Parallel Algorithms for String Matching with Wildcards
We study distributed algorithms for string matching problem in presence ...
read it

Computing Stackelberg Equilibria of Large GeneralSum Games
We study the computational complexity of finding Stackelberg Equilibria ...
read it

Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
Despite persistent efforts, there is no known technique for obtaining un...
read it

MapReduce Meets FineGrained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
read it

Optimal Strategies of Blotto Games: Beyond Convexity
The Colonel Blotto game, first introduced by Borel in 1921, is a wellst...
read it

Fast Algorithms for Knapsack via Convolution and Prediction
The knapsack problem is a fundamental problem in combinatorial optimizat...
read it

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce
The edit distance between two strings is defined as the smallest number ...
read it
Saeed Seddighin
is this you? claim profile