research
∙
08/30/2023
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Given a signed permutation on n elements, we need to sort it with the fe...
share
research
∙
04/03/2023
Compressed Indexing for Consecutive Occurrences
The fundamental question considered in algorithms on strings is that of ...
research
∙
03/13/2023
Optimal Square Detection Over General Alphabets
Squares (fragments of the form xx, for some string x) are arguably the m...
research
∙
02/02/2023
Optimal Heaviest Induced Ancestors
We revisit the Heaviest Induced Ancestors (HIA) problem that was introdu...
research
∙
02/01/2023
Order-Preserving Squares in Strings
An order-preserving square in a string is a fragment of the form uv wher...
research
∙
07/15/2022
Matching Patterns with Variables Under Edit Distance
A pattern α is a string of variables and terminal letters. We say that α...
research
∙
03/27/2022
Sublinear Dynamic Interval Scheduling (on one or multiple machines)
We revisit the complexity of the classical Interval Scheduling in the dy...
research
∙
01/14/2022
Cut query algorithms with star contraction
We study the complexity of determining the edge connectivity of a simple...
research
∙
11/09/2021
Pattern Matching on Grammar-Compressed Strings in Linear Time
The most fundamental problem considered in algorithms for text processin...
research
∙
11/02/2021
Finding the KT partition of a weighted graph in near-linear time
In a breakthrough work, Kawarabayashi and Thorup (J. ACM'19) gave a near...
research
∙
08/25/2021
Faster Exponential Algorithm for Permutation Pattern Matching
The Permutation Pattern Matching problem asks, given two permutations σ ...
research
∙
06/11/2021
Matching Patterns with Variables under Hamming Distance
A pattern α is a string of variables and terminal letters. We say that α...
research
∙
05/31/2021
Lower Bounds for the Number of Repetitions in 2D Strings
A two-dimensional string is simply a two-dimensional array. We continue ...
research
∙
05/13/2021
The Dynamic k-Mismatch Problem
The text-to-pattern Hamming distances problem asks to compute the Hammin...
research
∙
04/12/2021
The Theory of Universal Graphs for Infinite Duration Games
We introduce the notion of universal graphs as a tool for constructing a...
research
∙
03/04/2021
An Almost Optimal Edit Distance Oracle
We consider the problem of preprocessing two strings S and T, of lengths...
research
∙
02/23/2021
Conditional Lower Bounds for Variants of Dynamic LIS
In this note, we consider the complexity of maintaining the longest incr...
research
∙
02/14/2021
Fault-Tolerant Distance Labeling for Planar Graphs
In fault-tolerant distance labeling we wish to assign short labels to th...
research
∙
01/11/2021
Strictly In-Place Algorithms for Permuting and Inverting Permutations
We revisit the problem of permuting an array of length n according to a ...
research
∙
11/19/2020
Fully Dynamic Approximation of LIS in Polylogarithmic Time
We revisit the problem of maintaining the longest increasing subsequence...
research
∙
10/12/2020
Incomplete Directed Perfect Phylogeny in Linear Time
Reconstructing the evolutionary history of a set of species is a central...
research
∙
10/01/2020
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
Permutation σ appears in permutation π if there exists a subsequence of ...
research
∙
08/30/2020
Tight Bound for the Number of Distinct Palindromes in a Tree
For an undirected tree with n edges labelled by single letters, we consi...
research
∙
08/05/2020
A Note on a Recent Algorithm for Minimum Cut
Given an undirected edge-weighted graph G=(V,E) with m edges and n verti...
research
∙
07/16/2020
Substring Complexity in Sublinear Space
Shannon's entropy is a definitive lower bound for statistical compressio...
research
∙
07/12/2020
Efficient Labeling for Reachability in Digraphs
We consider labeling nodes of a directed graph for reachability queries....
research
∙
06/03/2020
Dynamic Longest Common Substring in Polylogarithmic Time
The longest common substring problem consists in finding a longest strin...
research
∙
05/03/2020
Efficiently Testing Simon's Congruence
Simon's congruence ∼_k is defined as follows: two words are ∼_k-equivale...
research
∙
03/30/2020
A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem
The Longest Common Increasing Subsequence (LCIS) is a variant of the cla...
research
∙
03/14/2020
Shorter Labels for Routing in Trees
A routing labeling scheme assigns a binary string, called a label, to ea...
research
∙
02/13/2020
On Two Measures of Distance between Fully-Labelled Trees
The last decade brought a significant increase in the amount of data and...
research
∙
01/16/2020
Generalised Pattern Matching Revisited
In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukris...
research
∙
01/05/2020
All non-trivial variants of 3-LDT are equivalent
The popular 3-SUM conjecture states that there is no strongly subquadrat...
research
∙
11/04/2019
Minimum Cut in O(mlog^2 n) Time
We give a randomized algorithm that finds a minimum cut in an undirected...
research
∙
07/28/2019
Minimal Absent Words in Rooted and Unrooted Trees
We extend the theory of minimal absent words to (rooted and unrooted) tr...
research
∙
05/07/2019
Even Faster Elastic-Degenerate String Matching via Fast Matrix Multiplication
An elastic-degenerate (ED) string is a sequence of n sets of strings of ...
research
∙
05/03/2019
RLE edit distance in near optimal time
We show that the edit distance between two run-length encoded strings of...
research
∙
02/12/2019
Compressed Range Minimum Queries
Given a string S of n integers in [0,σ), a range minimum query RMQ(i, j)...
research
∙
02/06/2019
Top Tree Compression of Tries
We present a compressed representation of tries based on top tree compre...
research
∙
12/17/2018
The complexity of mean payoff games using universal graphs
We study the computational complexity of solving mean payoff games. This...
research
∙
11/15/2018
Computing Quartet Distance is Equivalent to Counting 4-Cycles
The quartet distance is a measure of similarity used to compare two unro...
research
∙
11/05/2018
Almost Optimal Distance Oracles for Planar Graphs
We present new tradeoffs between space and query-time for exact distance...
research
∙
10/17/2018
Fast and Longest Rollercoasters
For k≥ 3, a k-rollercoaster is a sequence of numbers whose every maximal...
research
∙
09/07/2018
Streaming dictionary matching with mismatches
In the k-mismatch problem we are given a pattern of length m and a text ...
research
∙
07/04/2018
Near-Optimal Distance Emulator for Planar Graphs
Given a graph G and a set of terminals T, a distance emulator of G is an...
research
∙
06/25/2018
Fast entropy-bounded string dictionary look-up with mismatches
We revisit the fundamental problem of dictionary look-up with mismatches...
research
∙
04/26/2018
Edit Distance between Unrooted Trees in Cubic Time
Edit distance between trees is a natural generalization of the classical...
research
∙
02/15/2018
A Faster FPTAS for #Knapsack
Given a set W = {w_1,..., w_n} of non-negative integer weights and an in...
research
∙
01/03/2018