research
∙
09/11/2022
Dynamic Subset Sum with Truly Sublinear Processing Time
Subset sum is a very old and fundamental problem in theoretical computer...
share
research
∙
12/06/2021
On Complexity of 1-Center in Various Metrics
We consider the classic 1-center problem: Given a set P of n points in a...
research
∙
11/20/2021
Approximation Algorithms for LCS and LIS with Truly Improved Running Times
Longest common subsequence (𝖫𝖢𝖲) is a classic and central problem in com...
research
∙
07/09/2021
Optimal Space and Time for Streaming Pattern Matching
In this work, we study longest common substring, pattern matching, and w...
research
∙
01/18/2021
Dynamic Longest Increasing Subsequence and the Erdös-Szekeres Partitioning Problem
In this paper, we provide new approximation algorithms for dynamic varia...
research
∙
11/21/2020
Improved Dynamic Algorithms for Longest Increasing Subsequence
We study dynamic algorithms for the longest increasing subsequence (LIS)...
research
∙
11/21/2020
Erdös-Szekeres Partitioning Problem
In this note, we present a substantial improvement on the computational ...
research
∙
10/23/2020
Quantum Meets Fine-grained Complexity: Sublinear Time Quantum Algorithms for String Problems
Longest common substring (LCS), longest palindrome substring (LPS), and ...
research
∙
03/16/2020
Approximating LCS in Linear Time: Beating the √(n) Barrier
Longest common subsequence (LCS) is one of the most fundamental problems...
research
∙
03/06/2020
Learning Complexity of Simulated Annealing
Simulated annealing is an effective and general means of optimization. I...
research
∙
02/26/2020
Asymmetric Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
research
∙
02/26/2020
Streaming with Oracle: New Streaming Algorithms for Edit Distance and LCS
The edit distance (ED) and longest common subsequence (LCS) are two fund...
research
∙
10/25/2019
Massively Parallel Algorithms for String Matching with Wildcards
We study distributed algorithms for string matching problem in presence ...
research
∙
09/07/2019
Computing Stackelberg Equilibria of Large General-Sum Games
We study the computational complexity of finding Stackelberg Equilibria ...
research
∙
05/20/2019
Subcubic Equivalences Between Graph Centrality Measures and Complementary Problems
Despite persistent efforts, there is no known technique for obtaining un...
research
∙
05/05/2019
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark ...
research
∙
01/14/2019
Optimal Strategies of Blotto Games: Beyond Convexity
The Colonel Blotto game, first introduced by Borel in 1921, is a well-st...
research
∙
11/30/2018
Fast Algorithms for Knapsack via Convolution and Prediction
The knapsack problem is a fundamental problem in combinatorial optimizat...
research
∙
04/11/2018